COPSEQH - Non Coprime Sequences(Hard)

no tags 

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 109+7

Input

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

Constraints

  • 0 < n ≤ 105
  • 0 < m ≤ 1018

Output

Print the values of F(1, m), F(2, m) ... F(n, m) modulo 109+7 in a single line separated by space.

Example

Input:
2 10

Output:
4 7


Added by:Jatin
Date:2017-02-27
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own