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