Amr не любит математику, так как она кажется ему очень скучной, так что он обычно дремлет на парах по математике. Однажды преподаватель заподозрил: а не спит ли Amr? — и задал юноше вопрос, чтобы проверить это.
Сперва он дал Amr два положительных числа, n и k. Затем он спросил Amr, сколько существует таких целых чисел x > 0, что:
- Десятичная запись x (без ведущих нулей) состоит ровно из n цифр;
- Существует некоторое целое число y > 0, такое, что:
-
; - десятичная запись y является суффиксом десятичной записи x.
Так как ответ на этот вопрос может быть большим, преподаватель попросил Amr вычислить лишь остаток после деления результата на номер m.
Сможете помочь Amr достойно выйти из щекотливого положения?
Выходные данные
Выведите необходимое число по модулю m.
Примечание
Суффикс строки S — это непустая строка, которую можно получить путем удаления некоторого количества (возможно, нулевого) первых символов строки S.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 2 1000
|
4
|
|
2
|
2 2 1000
|
45
|
|
3
|
5 3 1103
|
590
|