Маленький полярный медвежонок Лимак нашёл в снегу свитки с древним пророчеством. Никаких древних языков он не знает, поэтому в пророчестве ему не разобраться, зато он знает цифры!
Один из фрагментов пророчества содержит последовательность из n цифр, причём первая из них не является нулём. Лимак полагает, что это последовательность каких-то годов. Пробелов и точек в записи нет, так что, возможно, древние люди их не использовали. Теперь Лимаку стало любопытно, какие же именно года фигурируют в фрагменте.
Медвежонок сделал следующие три предположения:
- Года записаны в порядке строгого возрастания;
- Каждый год обозначается целым положительным числом;
- Ведущие нули не используются.
Лимак хочет рассмотреть все возможные способы разбить данную последовательность цифр на числа (года), удовлетворяющие данным условиям. Он справится сам, без чьей либо помощи, однако попросил вас посчитать количество подходящих разбиений. Поскольку это число может быть достаточно большим, выведите его по модулю 109 + 7.
Примечание
В первом примере существует 8 способов разбить исходную последовательность:
- "123434" = "123434" (вся последовательность вполне может оказаться одним числом)
- "123434" = "1" + "23434"
- "123434" = "12" + "3434"
- "123434" = "123" + "434"
- "123434" = "1" + "23" + "434"
- "123434" = "1" + "2" + "3434"
- "123434" = "1" + "2" + "3" + "434"
- "123434" = "1" + "2" + "3" + "4" + "34"
Обратите внимание, что нельзя выполнить разбиение "123434" = "12" + "34" + "34", поскольку последовательность должна быть строго возрастающей.
Во втором примере существует 4 способа:
- "20152016" = "20152016"
- "20152016" = "20" + "152016"
- "20152016" = "201" + "52016"
- "20152016" = "2015" + "2016"