Со времен написания условия предыдущей задачи многое изменилось. Симпатичные узоры (о том, что это такое – см. задачу "Симпатичные узоры") стали очень популярны по всему миру, поэтому люди готовы содержать очень большой участок земли, лишь бы иметь на ней узор, не встречающийся больше нигде.
Теперь компания BrokenTiles является ведущим производителем симпатичных узоров в мире! Для составления плана исполнительному директору Васе по-прежнему необходимо знать, сколько клиентов могут рассчитывать на узор данных размеров.
Так как масштабы буквально мировые, N <= 10
100. Однако Вася не любит большие числа, поэтому просит выдать ответ по модулю P.
Входные данные
В первой строке входных данных содержатся три положительных целых числа, разделенные пробелом – N, M и P (1 <= N <= 10
100, 1 <= M <= 5, 1 <= P <= 10 000).
Выходные данные
Выведите количество различных симпатичных узоров N x M по модулю P .