首页 > 试题广场 >

Symmetric Matrix

[编程题]Symmetric Matrix
Count the number of n x n matrices A satisfying the following condition modulo m.
* Ai, j ∈ {0, 1, 2} for all 1 ≤ i, j ≤ n.
* Ai, j = Aj, i for all 1 ≤ i, j ≤ n.
* Ai, 1 + Ai, 2 + ... + Ai, n = 2 for all 1 ≤ i ≤ n.
* A1, 1 = A2, 2 = ... = An, n = 0.

输入描述:
The input consists of several test cases and is terminated by end-of-file.
Each test case contains two integers n and m.


输出描述:
For each test case, print an integer which denotes the result.
示例1

输入

3 1000000000
100000 1000000000

输出

1
507109376

备注:
* 1 ≤ n ≤ 105
* 1 ≤ m ≤ 109
* The sum of n does not exceed 107.

这道题你会答吗?花几分钟告诉大家答案吧!