COPSEQH - Non Coprime Sequences(Hard)
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 |