Codeshark round #1
A1. Rasta-lover Pair
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A pair (p, q) of integer numbers is called Rasta - lover if and only if 1 ≤ p, q < n and there is a positive integer like x such that:

px ≡ q (modn)

Subtasks 1 - 3:

Given n, calculate the number of Rasta - lover pairs modulo 109 + 7.

Subtasks 4 - 6:

A positive integer p is called n - Rastaly if and only if p < n and there is a positive integer like x such that px ≡ 1 (modn) and p and n are coprimes.

For a positive integer n, f(n) is the smallest positive integer a such that for each n - Rastaly number like p, pa ≡ 1 (modn) (this number always exists).

If M is equal to for a given A, then you have to calculate M modulo 109 + 7.

Subtasks:

  • Subtask A1: n = 1234
  • Subtask A2: n = 1111151
  • Subtask A3: n = 1234567
  • Subtask A4: A = 1234
  • Subtask A5: A = 12345
  • Subtask A6: A = 1234567
Input

Each subtask consists of one testcase.

Input consists of one number. For subtasks 1-3, it's n and for subtasks 4-6 it's A.

Output

Print the answer modulo 109 + 7 in one line.

Examples
A2. Rasta-lover Pair
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A pair (p, q) of integer numbers is called Rasta - lover if and only if 1 ≤ p, q < n and there is a positive integer like x such that:

px ≡ q (modn)

Subtasks 1 - 3:

Given n, calculate the number of Rasta - lover pairs modulo 109 + 7.

Subtasks 4 - 6:

A positive integer p is called n - Rastaly if and only if p < n and there is a positive integer like x such that px ≡ 1 (modn) and p and n are coprimes.

For a positive integer n, f(n) is the smallest positive integer a such that for each n - Rastaly number like p, pa ≡ 1 (modn) (this number always exists).

If M is equal to for a given A, then you have to calculate M modulo 109 + 7.

Subtasks:

  • Subtask A1: n = 1234
  • Subtask A2: n = 1111151
  • Subtask A3: n = 1234567
  • Subtask A4: A = 1234
  • Subtask A5: A = 12345
  • Subtask A6: A = 1234567
Input

Each subtask consists of one testcase.

Input consists of one number. For subtasks 1-3, it's n and for subtasks 4-6 it's A.

Output

Print the answer modulo 109 + 7 in one line.

Examples
A3. Rasta-lover Pair
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A pair (p, q) of integer numbers is called Rasta - lover if and only if 1 ≤ p, q < n and there is a positive integer like x such that:

px ≡ q (modn)

Subtasks 1 - 3:

Given n, calculate the number of Rasta - lover pairs modulo 109 + 7.

Subtasks 4 - 6:

A positive integer p is called n - Rastaly if and only if p < n and there is a positive integer like x such that px ≡ 1 (modn) and p and n are coprimes.

For a positive integer n, f(n) is the smallest positive integer a such that for each n - Rastaly number like p, pa ≡ 1 (modn) (this number always exists).

If M is equal to for a given A, then you have to calculate M modulo 109 + 7.

Subtasks:

  • Subtask A1: n = 1234
  • Subtask A2: n = 1111151
  • Subtask A3: n = 1234567
  • Subtask A4: A = 1234
  • Subtask A5: A = 12345
  • Subtask A6: A = 1234567
Input

Each subtask consists of one testcase.

Input consists of one number. For subtasks 1-3, it's n and for subtasks 4-6 it's A.

Output

Print the answer modulo 109 + 7 in one line.

Examples
A4. Rasta-lover Pair
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A pair (p, q) of integer numbers is called Rasta - lover if and only if 1 ≤ p, q < n and there is a positive integer like x such that:

px ≡ q (modn)

Subtasks 1 - 3:

Given n, calculate the number of Rasta - lover pairs modulo 109 + 7.

Subtasks 4 - 6:

A positive integer p is called n - Rastaly if and only if p < n and there is a positive integer like x such that px ≡ 1 (modn) and p and n are coprimes.

For a positive integer n, f(n) is the smallest positive integer a such that for each n - Rastaly number like p, pa ≡ 1 (modn) (this number always exists).

If M is equal to for a given A, then you have to calculate M modulo 109 + 7.

Subtasks:

  • Subtask A1: n = 1234
  • Subtask A2: n = 1111151
  • Subtask A3: n = 1234567
  • Subtask A4: A = 1234
  • Subtask A5: A = 12345
  • Subtask A6: A = 1234567
Input

Each subtask consists of one testcase.

Input consists of one number. For subtasks 1-3, it's n and for subtasks 4-6 it's A.

Output

Print the answer modulo 109 + 7 in one line.

Examples
A5. Rasta-lover Pair
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A pair (p, q) of integer numbers is called Rasta - lover if and only if 1 ≤ p, q < n and there is a positive integer like x such that:

px ≡ q (modn)

Subtasks 1 - 3:

Given n, calculate the number of Rasta - lover pairs modulo 109 + 7.

Subtasks 4 - 6:

A positive integer p is called n - Rastaly if and only if p < n and there is a positive integer like x such that px ≡ 1 (modn) and p and n are coprimes.

For a positive integer n, f(n) is the smallest positive integer a such that for each n - Rastaly number like p, pa ≡ 1 (modn) (this number always exists).

If M is equal to for a given A, then you have to calculate M modulo 109 + 7.

Subtasks:

  • Subtask A1: n = 1234
  • Subtask A2: n = 1111151
  • Subtask A3: n = 1234567
  • Subtask A4: A = 1234
  • Subtask A5: A = 12345
  • Subtask A6: A = 1234567
Input

Each subtask consists of one testcase.

Input consists of one number. For subtasks 1-3, it's n and for subtasks 4-6 it's A.

Output

Print the answer modulo 109 + 7 in one line.

Examples
A6. Rasta-lover Pair
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A pair (p, q) of integer numbers is called Rasta - lover if and only if 1 ≤ p, q < n and there is a positive integer like x such that:

px ≡ q (modn)

Subtasks 1 - 3:

Given n, calculate the number of Rasta - lover pairs modulo 109 + 7.

Subtasks 4 - 6:

A positive integer p is called n - Rastaly if and only if p < n and there is a positive integer like x such that px ≡ 1 (modn) and p and n are coprimes.

For a positive integer n, f(n) is the smallest positive integer a such that for each n - Rastaly number like p, pa ≡ 1 (modn) (this number always exists).

If M is equal to for a given A, then you have to calculate M modulo 109 + 7.

Subtasks:

  • Subtask A1: n = 1234
  • Subtask A2: n = 1111151
  • Subtask A3: n = 1234567
  • Subtask A4: A = 1234
  • Subtask A5: A = 12345
  • Subtask A6: A = 1234567
Input

Each subtask consists of one testcase.

Input consists of one number. For subtasks 1-3, it's n and for subtasks 4-6 it's A.

Output

Print the answer modulo 109 + 7 in one line.

Examples
B1. 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
B2. 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
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
C1. Dawn of the planet of the Rastas
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Due to the cruelties of Mike, Rastas attacked his country (to help its people of course) and they're moving forward to the capital.

Rastas' army has 2n - 1 soldiers and the strength of soldier number i is the number of set bits (bits equal to 1) in binary representation of number i (soldiers are numbered from 1 to 2n - 1).

If the greatest common divisor of numbers a and b is gcd(a, b), we know that strength of this army which we show with S is equal to:

As the minister of Mike, it's your duty to calculate S modulo 109 + 7.

Subtasks:

  • Subtask C1: n = 14
  • Subtask C2: n = 1234
  • Subtask C3: n = 12345678
Input

Each subtask consists of one testcase.

Input consists of one integer, n.

Output

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

Examples
C2. Dawn of the planet of the Rastas
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Due to the cruelties of Mike, Rastas attacked his country (to help its people of course) and they're moving forward to the capital.

Rastas' army has 2n - 1 soldiers and the strength of soldier number i is the number of set bits (bits equal to 1) in binary representation of number i (soldiers are numbered from 1 to 2n - 1).

If the greatest common divisor of numbers a and b is gcd(a, b), we know that strength of this army which we show with S is equal to:

As the minister of Mike, it's your duty to calculate S modulo 109 + 7.

Subtasks:

  • Subtask C1: n = 14
  • Subtask C2: n = 1234
  • Subtask C3: n = 12345678
Input

Each subtask consists of one testcase.

Input consists of one integer, n.

Output

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

Examples
C3. Dawn of the planet of the Rastas
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Due to the cruelties of Mike, Rastas attacked his country (to help its people of course) and they're moving forward to the capital.

Rastas' army has 2n - 1 soldiers and the strength of soldier number i is the number of set bits (bits equal to 1) in binary representation of number i (soldiers are numbered from 1 to 2n - 1).

If the greatest common divisor of numbers a and b is gcd(a, b), we know that strength of this army which we show with S is equal to:

As the minister of Mike, it's your duty to calculate S modulo 109 + 7.

Subtasks:

  • Subtask C1: n = 14
  • Subtask C2: n = 1234
  • Subtask C3: n = 12345678
Input

Each subtask consists of one testcase.

Input consists of one integer, n.

Output

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

Examples