B3. Rasta-making
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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
Input

Each subtask consists of one testcase.

Input consists of two integers, n and M.

Output

Print the answer modulo 109 + 7 in a single line.

Examples