You are given two integers, n and m.

Find and print the number of sequences of length n which satisfy:

•  All elements of the sequence are positive divisors of m
•  For any two adjacent elements, say p and q, there exists at least one prime which divides both of them.

Print the number of such sequences modulo 10⁹+7

Input

The only line of input contains two integers, n and m.

Constraints

• 0 < n ≤ 10⁵
• 0 < m ≤ 10¹⁸

Output

Print the number of valid sequences modulo 10⁹+7

Example

Input:
2 10
Output:
7