402239: GYM100705 B3 Rasta-making

Sequence of positive integers is given to you. A sequence of positive integers is called Rasta - made if and only if every two consecutive elements from this sequence are coprimes to each other.

A Rasta - making operation on a sequence consists of choosing two non-coprime consecutive elements from it and divide them both by one of their common prime factors. For example, we can turn the seqeunce to with performing one operation.

Phoulady number of a sequence is the minimum number of Rasta - making operations needed for turning it into a Rasta - made sequence.

Construction number of a a sequence is the number of different sequences we can get by performing 0 or more Rasta - making operations.

We show Phoulady number by F and Construction number by S.

In all subtasks:

• a₁ = 1426
• a_i = 1 + (1394a_i - 1 + 2015) modulo M (i > 1)

Subtasks:

• Subtask B1: n = 7890, M = 7901 and you should print S modulo 10⁹ + 7
• Subtask B2: n = 1234567, M = 1234577 and you should print S modulo 10⁹ + 7
• Subtask B3: n = 1234567, M = 1234577 and you should print F modulo 10⁹ + 7

Each subtask consists of one testcase.

Input consists of two integers, n and M.

Print the answer modulo 10⁹ + 7 in a single line.