Тролейбусний квиток має номер, що складається з шести цифр. Квиток вважається «щасливим», якщо сума перших трьох цифр дорівнює сумі останніх трьох, наприклад, 024321 (бо ~0+2+4=6=3+2+1~). Відомо, що кількість щасливих квитків із шести цифр (по три в кожній з половинок) дорівнює 55252.

Напишіть програму, яка розв'язує задачу підрахунку кількості «щасливих квитків» у загальному вигляді, а саме знаходить кількість «щасливих квитків» з ~2\cdot n~ цифр. Оскільки відповідь може бути досить великою, виведіть результат за модулем ~M~. (Тобто, виведіть залишок від ділення справжньої кількості квитків на ~M~. Однак, щоб це справді допомогло проти великих чисел, треба брати залишок від ділення не лише наприкінці, а й під час деяких із проміжних облислень.)

Вхідні дані

Програмі на вхід подається два числа ~n~ та ~M~ (~2\leqslant n \leqslant 20~, ~2 \leqslant M \leqslant 2^{30}~).

Результати

Виведіть одне число — кількість «щасливих квитків» з ~2\cdot n~ цифр за модулем ~M~.

Приклад

Вхід

3 1000000

Результат

55252