Good Bye 2015 |
---|
Закончено |
Маленький полярный медвежонок Лимак нашёл в снегу свитки с древним пророчеством. Никаких древних языков он не знает, поэтому в пророчестве ему не разобраться, зато он знает цифры!
Один из фрагментов пророчества содержит последовательность из n цифр, причём первая из них не является нулём. Лимак полагает, что это последовательность каких-то годов. Пробелов и точек в записи нет, так что, возможно, древние люди их не использовали. Теперь Лимаку стало любопытно, какие же именно года фигурируют в фрагменте.
Медвежонок сделал следующие три предположения:
Лимак хочет рассмотреть все возможные способы разбить данную последовательность цифр на числа (года), удовлетворяющие данным условиям. Он справится сам, без чьей либо помощи, однако попросил вас посчитать количество подходящих разбиений. Поскольку это число может быть достаточно большим, выведите его по модулю 109 + 7.
Первая строка входных данных содержит единственное число n (1 ≤ n ≤ 5000) — количество цифр в фрагменте пророчества.
Во второй строке записана строка длины n, состоящая только из цифр. Гарантируется, что первая цифра всегда не '0'.
Выведите количество способов корректно разбить последовательность цифр на числа по модулю 109 + 7.
6
123434
8
8
20152016
4
В первом примере существует 8 способов разбить исходную последовательность:
Обратите внимание, что нельзя выполнить разбиение "123434" = "12" + "34" + "34", поскольку последовательность должна быть строго возрастающей.
Во втором примере существует 4 способа:
Название |
---|