Limits 2s, 512 MB

I like short statements
and you should too
so here's the statement
without further ado

You are given 33 positive integers N,A,BN, A, B. You have to count the number of NN length positive integer arrays such that each of the elements of the array are divisors of BB and the greatest common divisor of the elements isAA.
Since the count can be large you have to output it modulo 10000000071000000007. In other words, if the count is XX, you have to output Xmod1000000007X \bmod 1000000007.


There will be TT independent testcases. First line of input will contain the positive integer TT. Next TT lines will each contain three positive integers N,A,BN, A, B separated by spaces.

1T1001 \leq T \leq 100
1N1091 \leq N \leq 10^{9}
1A,B10121 \leq A, B \leq 10^{12}


Output TT lines. The ii th line should have the answer for the ii th testcase.


2 2 16
1 5 15
3 6 15

In first testcase, there are 77 such arrays [2,2],[2,4],[2,8],[2,16],[4,2],[8,2],[16,2][2, 2], [2, 4], [2, 8], [2, 16], [4, 2], [8, 2], [16, 2]


Login to submit.


72% Solution Ratio
steinumEarliest, Feb '23
RU_CyberSquadFastest, 0.0s
masud_ali58Lightest, 4.9 MB
steinumShortest, 863B
Toph uses cookies. By continuing you agree to our Cookie Policy.