Сложность: 61%
На финансовом рынке новый игрок: К-банк. Неотъемлемой частью его маркетинга является число . Маркетологи вставляют его всюду и везде: это у них и процент по кредитам, и количество вкладок в приложении, и количество часов, которое вы проведёте в очереди за оформлением карты.
Как и в любом другом банке, перед каждой операцией в интернете клиентам приходит код подтверждения, состоящий из цифр от 0
до 9
. Маркетологи К-банка хотят, чтобы клиентам всегда приходил такой код, чтобы нашлась цифра, встречающаяся в этом коде ровно раз.
У службы безопасности возникли вопросы к безопасности этой фишки, ведь количество таких кодов может быть меньше, чем количество всех возможных кодов длины – а значит, его легче будет угадать. Помогите службе безопасности: посчитайте, сколько существует кодов длины , подходящих под критерий маркетологов.
Входные данные
В единственной строке через пробел записаны два числа и ().
Выходные данные
В единственной строке выведите одно число – количество таких кодов длины , что найдётся цифра, встречающаяся в коде ровно раз.
Так как ответ может быть очень большим, выведите его по модулю .
Подзадачи
№ | баллы | необх. подзадачи | ограничения |
1 | 5 | - | |
2 | 20 | 1 | |
3 | 30 | 2 | |
4 | 15 | - | |
5 | 10 | 4 | |
6 | 20 | 3, 5 | Нет дополнительных ограничений |
STDIN | STDOUT |
4 2 | 4590 |
6 2 | 735750 |