In a now finished competition, I stumbled across a task that I didn't manage to solve it.
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 10^9+7
0 < n ≤ 10^5
0 < m ≤ 10^18
Here's link to the full task description.
Can somebody explain to me solution to this problem in detail?