On a beautiful day, Marisa and Reimu went mushroom harvesting in the forest to give them to Reisen. The forest has a total of n−1 mushrooms, with the i-th mushroom having the color i+1. Marisa and Reimu will each harvest some mushrooms and put them in their baskets (they may possibly harvest none). Because they adore Reisen a lot, they want their two baskets of mushrooms to be as perfect as possible. According to Marisa and Reimu, two baskets of mushrooms are considered perfect if there doesn't exist a way to choose a mushroom with color x from the first basket and a mushroom with color y from the second basket such that gcd(x,y)>1. Count the number of ways for the two of them to harvest mushrooms so that their baskets are perfect. Given a positive integer p, print the answer modulo p.
### Input
- Consists of two positive integers n,p.
### Output
- Print a single line containing the answer of the problem modulo p.
### Constraints
- 2≤n≤500.
- 1≤p≤109.
### Example
Input:
31000000
Output:
9
Input:
41000
Output:
21
Input:
50100000
Output:
45307
Input:
1231000000
Output:
972901
### Subtask
- 30 of the tests have 2≤n≤30.
- 20 of the tests have 2≤n≤100.
- 50 of the tests have 2≤n≤500.
