Ненульові ПрефСуф суми

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

Принц Чармінг хотів розповісти вам довгу, нудну легенду, сповнену помпезності й пишності. Але Шрек цього не дозволив! Натомість він дає вам повністю формальну й коротку задачу.

Порахуйте кількість масивів \([a_1, a_2, \dots, a_n]\) цілих чисел, які задовольняють наступні умови:

1. \(|a_i| \leq m\) для всіх \(1 \leq i \leq n\).

2. Існує перестановка \([b_1, b_2, \dots, b_n]\) елементів масиву \(a\), щоб виконувалися наступні умови:

   • \(b_1 + b_2 + \dots + b_k \neq 0\) для всіх \(1 \leq k \leq n\).

   • \(b_k + b_{k+1} + \dots + b_n \neq 0\) для всіх \(1 \leq k \leq n\).

Порахуйте відповідь за модулем \(p\), де \(p\) — це велике просте число.

Вхідні дані

У єдиному рядку задано три цілі числа \(n\), \(m\) та \(p\).

Вихідні дані

Виведіть ціле число — відповідь на задачу за модулем \(p\).

Обмеження

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

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

\(10^8 < p < 10^9\), \(p\) — просте.

Приклади

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

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

Примітки

У першому прикладі є \(9\) можливих масивів: \([-1, -1]\), \([-1, 0]\), \([-1, 1]\), \([0, -1]\), \([0, 0]\), \([0, 1]\), \([1, -1]\), \([1, 0]\), \([1, 1]\). Масиви \([-1, -1]\) та \([1, 1]\) задовольняють умову задачі.