Задача №112029. Несостоявшийся программист
Был обычный весенний вечер. За окном завывала метель. Бухгалтер Евгений скучал на работе и с грустью вспоминал о своих былых успехах на олимпиадах по программированию. В его школьные годы на олимпиадах давали не больше восьми задач, и, разглядывая график своих успехов на сайте Topforces, ему удалось подсчитать, что в \(v_1\) олимпиадах он решил ровно 1 задачу, в \(v_2\) олимпиадах — ровно 2, \(\ldots\), в \(v_8\) олимпиадах — ровно 8 задач (Евгений предпочитал не вспоминать об олимпиадах, на которых он ничего не решил). К концу рабочего дня в офисе не осталось чистой бумаги, а из всех электронных устройств включенным оставался только калькулятор. Нашему герою ничего другого не оставалось, кроме как ввести памятные ему числа в калькулятор: \(v_1 1 v_2 2 \ldots v_8 8\). Стоит заметить, что никаких пробелов и других разделителей на калькуляторе Евгения не было, поэтому он записал эти числа просто подряд, получив некоторое число \(N\). Кроме того, он был достаточно ленив, поэтому все \(v_i\) вводил без ведущих нулей, а если какое-то \(v_i\) равнялось нулю, то соответствующую пару \(v_i i\) он просто не вводил.
Например, если \(v_2 = 111\), \(v_3 = 1\), а все остальные \(v_i = 0\), то у Евгения получилось бы число \(N = 111213\).
Уйдя с работы, Евгений оставил калькулятор с введенным числом \(N\) на столе, чем и воспользовалась его любопытная коллега Марина. Она сразу догадалась, как образовано введенное число, и уже собиралась приступать к расшифровке, как вдруг поняла, что различных наборов \((v_1, \ldots, v_8)\), из которых можно было получить это число, может быть достаточно много. Так, приведенное выше число \(N\) может быть получено также и при \(v_1 = 11\), \(v_3 = 21\).
Марина попросила вас найти количество таких наборов по модулю числа \(1\,000\,000\,007 = 10^9 + 7\).
Входной файл содержит единственное оставленное Евгением на калькуляторе целое число \(N\) (\(1 \leqslant N \lt 10^{1\,000\,000}\)).
Выведите единственное целое число количество различных наборов \((v_1, . . . , v_8)\), из которых описанным выше алгоритмом можно было получить число \(N\) , по модулю числа \(10^9 + 7\).
Два набора \((v_1, . . . , v_8)\) и \((v′_1, . . . , v′_8)\) будем считать различными, если хотя бы для одного \(i\) от \(1\) до \(8\) \(v_i \ne v′_i\).
Обратите внимание, что Евгений мог ошибиться и получить число \(N\), которое не соответствует ни одному набору \((v_1, . . . , v_8)\).
- Подзадача 0 (0 баллов) тест из условия.
- Подзадача 1 (30 баллов) в тестах этой группы \(1 \le N \lt 10^{10}\). Необходимые подгруппы: 0.
- Подзадача 2 (30 баллов) в тестах этой группы \(1\le N \lt 10^{1000}\). Необходимые подгруппы: 0-1.
- Подзадача 3 (40 баллов) без дополнительных ограничений. Необходимые подгруппы: 0-2.
111213
5