Принц Чармінг хотів розповісти вам довгу, нудну легенду, сповнену помпезності й пишності. Але Шрек цього не дозволив! Натомість він дає вам повністю формальну й коротку задачу.
Порахуйте кількість масивів [a_1, a_2, \dots, a_n] цілих чисел, які задовольняють наступні умови:
|a_i| \leq m для всіх 1 \leq i \leq n.
Існує перестановка [b_1, b_2, \dots, b_n] елементів масиву , щоб виконувалися наступні умови: 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.
Порахуйте відповідь за модулем , де — це велике просте число.
У єдиному рядку задано три цілі числа , та .
2 \leq n \leq 100,
1 \leq m \leq 100,
10^8 < p < 10^9, — просте.
Виведіть ціле число — відповідь на задачу за модулем .
Приклад
Приклад 1
У першому прикладі є можливих масивів: , , , , , , , , . Масиви та задовольняють умову задачі.