시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 169 24 16 34.043%

문제

창영이는 비밀번호를 만드는 함수가 있다.

이 함수의 뜻은 최소공배수가 n인 모든 쌍을 찾아, 그 합을 구하는 것이다.

예를 들어, 최소공배수가 6인 쌍은 5가지가 있다. (1, 6), (2, 6), (2, 3), (3, 6), (6, 6)

따라서 f(6)은 f(6) = (1+6) + (2+6) + (2+3) + (3+6) + (6+6) = 7+8+5+9+12 = 41 이 된다.

창영이의 온라인 저지 비밀번호를 만든 n이 주어졌을 때, 비밀번호를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (T ≤ 500)

각 테스트 케이스의 첫째 줄에는 C가 주어진다. (C ≤ 15) C는 n의 소인수의 개수이다.

다음 C개 줄에는 소인수 Pi와 그것의 개수 ai가 주어진다. (2 ≤ Pi ≤ 1000, Pi는 소수, 1 ≤ ai ≤ 50) 입력으로 주어지는 소수는 모두 서로 다르다.

출력

각 테스트 케이스에 대해서, 한 줄에 하나씩 f(n)값을 1000000007으로 나눈 나머지를 출력한다.

예제 입력 1

3
2
2 1
3 1
2
2 2
3 1
1
5 1

예제 출력 1

41
117
16
W3sicHJvYmxlbV9pZCI6IjM4MDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZTBcdWNjM2RcdWM2MDEgXHViZTQ0XHViYzAwXHViYzg4XHVkNjM4XHVjNzU4IFx1YmU0NFx1YmMwMCIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0XHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YmU0NFx1YmMwMFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVkNTY4XHVjMjE4XHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9kYXVtX2VxdWF0aW9uXzEzNTc3NjAzMjgyMTQucG5nXCIgXC8+PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc3NCBcdWQ1NjhcdWMyMThcdWM3NTggXHViNzNiXHVjNzQwIFx1Y2Q1Y1x1YzE4Y1x1YWNmNVx1YmMzMFx1YzIxOFx1YWMwMCBuXHVjNzc4IFx1YmFhOFx1YjRlMCBcdWMzMGRcdWM3NDQgXHVjYzNlXHVjNTQ0LCBcdWFkZjggXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1Y2Q1Y1x1YzE4Y1x1YWNmNVx1YmMzMFx1YzIxOFx1YWMwMCA2XHVjNzc4IFx1YzMwZFx1Yzc0MCA1XHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gKDEsIDYpLCAoMiwgNiksICgyLCAzKSwgKDMsIDYpLCAoNiwgNik8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViNTMwXHViNzdjXHVjMTFjIGYoNilcdWM3NDAgZig2KSA9ICgxKzYpICsgKDIrNikgKyAoMiszKSArICgzKzYpICsgKDYrNikgPSA3KzgrNSs5KzEyID0gNDEgXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjYzNkXHVjNjAxXHVjNzc0XHVjNzU4IFx1YzYyOFx1Yjc3Y1x1Yzc3OCBcdWM4MDBcdWM5YzAgXHViZTQ0XHViYzAwXHViYzg4XHVkNjM4XHViOTdjIFx1YjljY1x1YjRlMCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmU0NFx1YmMwMFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChUICZsZTsgNTAwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoQyAmbGU7IDE1KSBDXHViMjk0IG5cdWM3NTggXHVjMThjXHVjNzc4XHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIENcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzE4Y1x1Yzc3OFx1YzIxOCBQPHN1Yj5pPFwvc3ViPlx1YzY0MCBcdWFkZjhcdWFjODNcdWM3NTggXHVhYzFjXHVjMjE4IGE8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBQPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDAsIFA8c3ViPmk8XC9zdWI+XHViMjk0IFx1YzE4Y1x1YzIxOCwgMSAmbGU7IGE8c3ViPmk8XC9zdWI+ICZsZTsgNTApIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjMThjXHVjMjE4XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc0XHViMmU0LjxcL3A+XHJcblxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IGYobilcdWFjMTJcdWM3NDQgMTAwMDAwMDAwN1x1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzODA3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTENNIFBhaXIgU3VtIiwiZGVzY3JpcHRpb24iOiI8cD5PbmUgb2YgeW91ciBmcmllbmRzIGRlc3BlcmF0ZWx5IG5lZWRzIHlvdXIgaGVscC4gSGUgaXMgd29ya2luZyB3aXRoIGEgc2VjcmV0IGFnZW5jeSBhbmQgZG9pbmcgc29tZSBlbmNvZGluZyBzdHVcdWZiMDBzLiBBcyB0aGUgbWlzc2lvbiBpcyBjb25maWRlbnRpYWwgaGUgZG9lcyBub3QgdGVsbCB5b3UgbXVjaCBhYm91dCB0aGF0LCBoZSBqdXN0IHdhbnQgeW91IHRvIGhlbHAgaGltIHdpdGggYSBzcGVjaWFsIHByb3BlcnR5IG9mIGEgbnVtYmVyLiBUaGlzIHByb3BlcnR5IGNhbiBiZSBleHByZXNzZWQgYXMgYSBmdW5jdGlvbiBmKG4pIGZvciBhIHBvc2l0aXZlIGludGVnZXIgbi4gSXQgaXMgZGVmaW5lZCBhczo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9sY21wcy5wbmdcIiBzdHlsZT1cImhlaWdodDo3NHB4OyB3aWR0aDoxNzdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5JbiBvdGhlciB3b3JkcywgaGUgbmVlZHMgdGhlIHN1bSBvZiBhbGwgcG9zc2libGUgcGFpcnMgd2hvc2UgbGVhc3QgY29tbW9uIG11bHRpcGxlIGlzIG4uIChUaGUgbGVhc3QgY29tbW9uIG11bHRpcGxlIChMQ00pIG9mIHR3byBudW1iZXJzIHAgYW5kIHEgaXMgdGhlIGxvd2VzdCBwb3NpdGl2ZSBpbnRlZ2VyIHdoaWNoIGNhbiBiZSBwZXJmZWN0bHkgZGl2aWRlZCBieSBib3RoIHAgYW5kIHEpLiBGb3IgZXhhbXBsZSwgdGhlcmUgYXJlIDUgZGlcdWZiMDBlcmVudCBwYWlycyBoYXZpbmcgdGhlaXIgTENNIGVxdWFsIHRvIDYgYXMgKDEsIDYpLCAoMiwgNiksICgyLCAzKSwgKDMsIDYpLCAoNiwgNikuIFNvIGYoNikgaXMgY2FsY3VsYXRlZCBhcyBmKDYpID0gKDEgKyA2KSArICgyICsgNikgKyAoMiArIDMpICsgKDMgKyA2KSArICg2ICsgNikgPSA3ICsgOCArIDUgKyA5ICsgMTIgPSA0MS48XC9wPlxyXG5cclxuPHA+WW91ciBmcmllbmQga25vd3MgeW91IGFyZSBnb29kIGF0IHNvbHZpbmcgdGhpcyBraW5kIG9mIHByb2JsZW1zLCBzbyBoZSBhc2tlZCB5b3UgdG8gbGVuZCBhIGhhbmQuIEhlIGFsc28gZG9lcyBub3Qgd2FudCB0byBkaXN0dXJiIHlvdSBtdWNoLCBzbyB0byBhc3Npc3QgeW91IGhlIGhhcyBmYWN0b3JpemVkIHRoZSBudW1iZXIuIEhlIHRoaW5rcyBpdCBtYXkgaGVscCB5b3UuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCB3aWxsIGNvbnRhaW4gdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgKFQgJmxlOyZuYnNwOzUwMCkuIEFmdGVyIHRoYXQgdGhlcmUgd2lsbCBiZSBUIHRlc3QgY2FzZXMuIEVhY2ggb2YgdGhlIHRlc3QgY2FzZXMgd2lsbCBzdGFydCB3aXRoIGEgcG9zaXRpdmUgbnVtYmVyIEMgKEMgJmxlOyZuYnNwOzE1KSBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHByaW1lIGZhY3RvcnMgb2Ygbi4gVGhlbiB0aGVyZSB3aWxsIGJlIEMgbGluZXMgZWFjaCBjb250YWluaW5nIHR3byBudW1iZXJzIFA8c3ViPmk8XC9zdWI+IGFuZCBhPHN1Yj5pPFwvc3ViPiBkZW5vdGluZyB0aGUgcHJpbWUgZmFjdG9yIGFuZCBpdHMgcG93ZXIgKFA8c3ViPmk8XC9zdWI+IGlzIGEgcHJpbWUgYmV0d2VlbiAyIGFuZCAxMDAwKSBhbmQgKDEgJmxlOyZuYnNwO2E8c3ViPmk8XC9zdWI+Jm5ic3A7JmxlOyZuYnNwOzUwKS4gQWxsIHRoZSBwcmltZXMgZm9yIGFuIGlucHV0IGNhc2Ugd2lsbCBiZSBkaXN0aW5jdC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBvZiB0aGUgdGVzdCBjYXNlcyBwcm9kdWNlIG9uZSBsaW5lIG9mIG91dHB1dCBkZW5vdGluZyB0aGUgY2FzZSBudW1iZXIgYW5kIGYobikgbW9kdWxvIDEwMDAwMDAwMDcuIFNlZSB0aGUgb3V0cHV0IGZvciBzYW1wbGUgaW5wdXQgZm9yIGV4YWN0IGZvcm1hdHRpbmcuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d