SP30945 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 10 $ ^{9} $ +7

The only line of input contains two integers, n and m. #### Constraints - 0 < n - 0 < m

Print the number of valid sequences modulo 10 $ ^{9} $ +7