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

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

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] елементів масиву , щоб виконувалися наступні умови: b_1 + b_2 + \dots + b_k \neq 0 для всіх 1 \leq k \leq n.

  3. 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, — просте.

Вихідні дані

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

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

У першому прикладі є можливих масивів: , , , , , , , , . Масиви та задовольняють умову задачі.