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?