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