NonZero PrefSuf Sums

Обмеження: 2 сек., 512 МіБ

Prince Charming wanted to give you a long, tedious legend full of pomp and flair. But Shrek won’t allow this! He gives you a completely formal and short statement instead.

Count the number of arrays \([a_1, a_2, \dots, a_n]\) of integers that satisfy the following conditions:

1. \(|a_i| \leq m\) for all \(1 \leq i \leq n\).

2. There exists a permutation \([b_1, b_2, \dots, b_n]\) of elements of \(a\), such that the following holds:

   • \(b_1 + b_2 + \dots + b_k \neq 0\) for all \(1 \leq k \leq n\).

   • \(b_k + b_{k+1} + \dots + b_n \neq 0\) for all \(1 \leq k \leq n\).

Output the answer modulo \(p\), where \(p\) is a big prime number.

Вхідні дані

The only line of the input contains three integers \(n\), \(m\), \(p\).

Вихідні дані

Output a single integer — the answer modulo \(p\).

Обмеження

\(2 \leq n \leq 100\),

\(1 \leq m \leq 100\),

\(10^8 < p < 10^9\), \(p\) is prime.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 1 998244353	2

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
69 42 696969697	378553557

Примітки

In the first test case, there are \(9\) possible arrays: \([-1, -1]\), \([-1, 0]\), \([-1, 1]\), \([0, -1]\), \([0, 0]\), \([0, 1]\), \([1, -1]\), \([1, 0]\), \([1, 1]\). Only arrays \([-1, -1]\) and \([1, 1]\) satisfy the condition from the problem.