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