D. Новый год и древнее пророчество
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленький полярный медвежонок Лимак нашёл в снегу свитки с древним пророчеством. Никаких древних языков он не знает, поэтому в пророчестве ему не разобраться, зато он знает цифры!

Один из фрагментов пророчества содержит последовательность из n цифр, причём первая из них не является нулём. Лимак полагает, что это последовательность каких-то годов. Пробелов и точек в записи нет, так что, возможно, древние люди их не использовали. Теперь Лимаку стало любопытно, какие же именно года фигурируют в фрагменте.

Медвежонок сделал следующие три предположения:

  • Года записаны в порядке строгого возрастания;
  • Каждый год обозначается целым положительным числом;
  • Ведущие нули не используются.

Лимак хочет рассмотреть все возможные способы разбить данную последовательность цифр на числа (года), удовлетворяющие данным условиям. Он справится сам, без чьей либо помощи, однако попросил вас посчитать количество подходящих разбиений. Поскольку это число может быть достаточно большим, выведите его по модулю 109 + 7.

Входные данные

Первая строка входных данных содержит единственное число n (1 ≤ n ≤ 5000) — количество цифр в фрагменте пророчества.

Во второй строке записана строка длины n, состоящая только из цифр. Гарантируется, что первая цифра всегда не '0'.

Выходные данные

Выведите количество способов корректно разбить последовательность цифр на числа по модулю 109 + 7.

Примеры
Входные данные
6
123434
Выходные данные
8
Входные данные
8
20152016
Выходные данные
4
Примечание

В первом примере существует 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"