NOI '15 P3 - Sushi Dinner

View as PDF

Submit solution

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

Problem type

Compute the number of ways to choose two subsets X, Y \subseteq \{2, 3, \dots, n\} such that there does not exist x \in X, y \in Y such that x and y are not relatively prime. The sets X, Y may be empty. Output the number of ways modulo p.

Input Specification

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

Output Specification

Output the number of ways to choose the subsets X, Y \subseteq \{2, 3, \dots, n\} 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

Constraints

Test CasenAdditional Constraints
12 \le n \le 300 < p \le 1\,000\,000\,000
2
3
42 \le n \le 100
5
62 \le n \le 200
7
82 \le n \le 500
9
10

Comments

There are no comments at the moment.