Компанія \textit{BrokenTiles} плаує зайнятись викладування у подвір'ях заможних клієнтів візерунок з чорних та білих плиток, кожна з яких має розмір \textbf{1}×\textbf{1} метр. Відомо, що подвір'я усіх заможних людей мають найбільш модну на сьогодні форму прямокутника \textbf{n}×\textbf{m} метрів. Проте при складанні фінансового плану у директора цієї організації виявилось цілих дві серйозних проблеми: по-перше, кожен новий клієнт очевидно захоче, щоб візерунок, викладений у нього на подвір'ї, відрізнявся від візерунків усіх інших клієнтів цієї фірми, і по-друге, цей візерунок повинен бути симпатичним. Як показали дослідження,візерунок є симпатичним, якщо у ньому ніде не зустрічається квадрат \textbf{2}×\textbf{2} метри, повністю покритий плитками одного кольору. Для складання фінансового плану директору необхідн знати, скільки клієнтів він зможе обслужити, до того як симпатичні візерунки даного розміру закінчаться. Допоможіть йому! \InputFile У першому рядку вхідного файлу знаходиться три натуральних числа \textbf{n}, \textbf{m} та \textbf{p }(\textbf{1} ≤ \textbf{n} ≤ \textbf{10^100}, \textbf{1} ≤ \textbf{m} ≤ \textbf{5}, \textbf{1}≤ \textbf{p} ≤ \textbf{10000}). \OutputFile Виведіть у вихідний файл єдине число --- кількість різних симпатичних візерунків, які можна викласти на подвір'ї розміром \textbf{n}×\textbf{m} по модулю \textbf{p}. Візерунки, отримані один з одного зсувом, поворотом чи віддзеркаленням вважаються різними.