У задачу «Щасливі квитки – 1» прийшов забобоноактивіст №1 і сказав: «Офіційна наука все'дно не визнає поняття щасливого квитка, і тому визначати, чи квиток щасливий чи ні, буду я. З ідеєю, що сума цифр у лівій половині має дорівнювати сумі цифр у правій половині, погодитися можна. Але ж числа, які містять в собі 666, не можуть бути щасливими! Отже, рахуйте кількість тих щасливих квитків, де водночас:

• сума цифр лівої половини дорівнює сумі цифр правої половини;
• число не містить трьох (чи ще більшої кількості) цифр 6 підряд.»

Напишіть програму, яка рахуватиме кількість щасливих (з урахуванням побажань пана забобоноактивіста №1) квитків з ~2\cdot n~ десятковими цифрами (по ~n~ у кожній половинці) за модулем ~M~.

Вхідні дані

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

Результати

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

Приклад

Вхід

3 1000000

Результат

55020

Примітка

Ті 232 числа, які є щасливими з точки зору задачі «Щасливі квитки – 1», але не є щасливими з точки зору цієї задачі, можна побачити за цим посиланням.