Define F(n, m) to be 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.

You are given two integers, n and m. Find the values of F(1, m), F(2, m), ... F(n, m) 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 values of F(1, m), F(2, m) ... F(n, m) modulo 10⁹+7 in a single line separated by space.

Example

Input:
2 10

Output:
4 7