Макс стал сотрудником нового телефонного оператора.
Макс узнал, что телефонные номера у этого оператора состоят из N цифр, и всего есть K номеров. Первый из них называется стартовым и равен S, а все остальные последовательно генерируются по следующему правилу: i-я цифра очередного номера телефона равна цифровому корню суммы первых i цифр предыдущего номера телефона.
Цифровой корень любой цифры равен самой этой цифре. Цифровой корень любого числа равен цифровому корню суммы его цифр. Например, цифровой корень числа 65536 равен 7, потому что 6 + 5 + 5 + 3 + 6 = 25 и 2 + 5 = 7.
Макс знает стартовый номер, на основе которого оператор генерирует остальные номера телефонов, и теперь хочет выяснить, сколько раз в получившихся K номерах будет встречаться каждая из десятичных цифр. Помогите Максу найти ответ на этот вопрос.