402239: GYM100705 B3 Rasta-making
Description
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:
- a1 = 1426
- ai = 1 + (1394ai - 1 + 2015) modulo M (i > 1)
Subtasks:
- Subtask B1: n = 7890, M = 7901 and you should print S modulo 109 + 7
- Subtask B2: n = 1234567, M = 1234577 and you should print S modulo 109 + 7
- Subtask B3: n = 1234567, M = 1234577 and you should print F modulo 109 + 7
Each subtask consists of one testcase.
Input consists of two integers, n and M.
OutputPrint the answer modulo 109 + 7 in a single line.
Examples