Sum of d-th Power of Coprime Numbers

Given a non-negative integer (d) and a positive integer (n), define [ f_d(n) = \sum_{\substack{1 \leq i < n \ \gcd(i,n)=1}} i^d ] For example, (f_3(10) = 1^3 + 3^3 + 7^3 + 9^3 = 1100).

Your task is to compute (f_d(n) \mod (10^9+7)) given (d) and (n).

Note: When (d=0), every (i^0 = 1), so (f_0(n)) is simply the count of integers less than (n) that are coprime with (n).

hjy96 may have his own solution, but now it's your turn to solve it!

inputFormat

The input consists of two space-separated integers (d) and (n), where (d) is a non-negative integer and (n) is a positive integer.

outputFormat

Output a single integer, the value of (f_d(n) \mod (10^9+7)).

sample

3 10

1100