COPSEQ - Non Coprime Sequences
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 109+7
Input
The only line of input contains two integers, n and m.
Constraints
- 0 < n ≤ 105
- 0 < m ≤ 1018
Output
Print the number of valid sequences modulo 109+7
Example
Input: 2 10 Output: 7
Print the number of such sequences modulo 10^9 + 7
hide comments
Vipul Srivastava:
2017-02-26 12:06:48
@Jatin can you explain the test case?
|
Added by: | Jatin |
Date: | 2017-02-26 |
Time limit: | 4s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Own |