Hái nấm III

Vào một ngày đẹp trời, Alice và Reimu đi hái nấm trong khu rừng để đem tặng cho Reisen. Khu rừng có tất cả \(n-1\) cây nấm, cây nấm thứ \(i\) mang màu sắc \(i+1\). Alice và Reimu mỗi người sẽ hái một số cây nấm và bỏ vào giỏ của họ (có thể không hái cây nào).

Vì rất yêu quý Reisen, họ muốn hai giỏ nấm của mình phải hoàn hảo nhất có thể. Theo Alice và Reimu, hai giỏ nấm được coi là hoàn hảo nếu không tồn tại một cách chọn một cây nấm có màu \(x\) từ giỏ thứ nhất và một cây nấm có màu \(y\) từ giỏ thứ hai sao cho \(gcd(x,y) > 1\).

Hãy đếm số cách hái nấm của hai người để hai giỏ nấm của họ là hoàn hảo. Cho một số nguyên dương \(p\), in ra đáp án modulo \(p\).

Input

Gồm một dòng duy nhất chứa hai số nguyên dương \(n, p\) (\(2 \le n \le 500\), \(1 \le p \le 10^9\)).

Ràng buộc:

• Có \(30\%\) số test có \(2 \le n \le 30\).

• Có \(20\%\) số test có \(2 \le n \le 100\).

• Có \(50\%\) số test có \(2 \le n \le 500\).

Output

In ra một dòng chứa đáp án của bài toán modulo \(p\).

Example 1

Input:

3 1000000

Output:

9

Example 2

Input:

4 1000

Output:

21

Example 3

Input:

50 100000

Output:

45307

Example 4

Input:

123 1000000

Output:

972901

Note

Với bộ dữ liệu thứ nhất: \(n=3\), miền màu sắc của nấm là \(\{2,3\}\). Mỗi giỏ là một tập con (có thể rỗng) của \(\{2,3\}\), nên có \(4 \times 4 = 16\) cặp giỏ. Một cặp giỏ không hoàn hảo khi cả hai giỏ cùng chứa màu \(2\) (vì \(gcd(2,2)=2>1\)) hoặc cả hai giỏ cùng chứa màu \(3\) (vì \(gcd(3,3)=3>1\)). Có \(9\) cặp giỏ hoàn hảo trong số \(16\) cặp, nên đáp số là \(9\).