COPSEQ - Non Coprime Sequences

no tags 

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?
(jatin) -> the valid sequences are (2,2), (2,10), (5,5), (5,10), (10,2), (10,5), (10,10)

Last edit: 2017-02-26 14:37:18

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