## NOI '15 P3 - Sushi Dinner

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Compute the number of ways to choose two subsets such that there does not exist such that and are not relatively prime. The sets may be empty. Output the number of ways modulo .

#### Input Specification

The input contains the integer and the modulo separated by a space.

#### Output Specification

Output the number of ways to choose the subsets satisfying the condition above.

#### Sample Input 1

3 10000

#### Sample Output 1

9

#### Sample Input 2

4 10000

#### Sample Output 2

21

#### Sample Input 3

100 100000000

#### Sample Output 3

3107203

1
2
3
4
5
6
7
8
9
10