Симпатичные узоры 2 Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узоров из черных и белых плиток, каждая из которых имеет размер 1?1 метр. Известно, что

Симпатичные узоры 2
Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узоров из черных и белых плиток, каждая из которых имеет размер 1Ч1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника размером MЧN метров.
Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во первых, каждый новый клиент очевидно захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных клиентов этой фирмы, а во вторых, этот узор должен быть симпатичным.
Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2Ч2 метра, полностью покрытого плитками одного цвета. На рисунке 1 показаны примеры различных симпатичных узоров, а на рисунке 2 – несимпатичных.
[ Cкачайте файл, чтобы посмотреть картинку ] [ Cкачайте файл, чтобы посмотреть картинку ] Рисунок 1 Рисунок 2

Для составления финансового плана директору необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!
На этот раз его интересует долгосрочная перспектива, поэтому N ( 10100. Однако он не любит большие числа, поэтому просит выдать ответ по модулю P.
Формат входных данных
На первой строке входного файла находятся три положительных целых числа, разделенные пробелом – N, M и P (1
· N
· 10100, 1
· M
· 5, 1
· P
· 10000).
Формат выходных данных
Выведите в выходной файл количество различных симпатичных узоров MЧN по модулю P.
Примеры
Input
Output

2 2 5
4

3 3 23
0


Зимние учебно-тренировочные сборы
17 февраля 2003 года

Страница 13 PAGE 14115 из 2




Приложенные файлы

  • doc 6954845
    Размер файла: 30 kB Загрузок: 2

Добавить комментарий