100 БАЛЛОВ
Утраченный символ
Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Стёпа очень любит многоуровневые компьютерные игры. Особенно ему нравятся те игры, в
которых в любой момент можно узнать, на каком по счету уровне он сейчас находится и сколько
всего уровней имеется в этой игре. Обычно где-нибудь в углу экрана находится надпись, например
«10/100», которая означает, что сейчас Стёпа находится на 10 уровне, а всего в игре 100 уровней.
На днях Стёпа установил на свой компьютер новую игру, но оказалось, что разработчик для вывода на экран надписи с номерами уровней использовал шрифт, которого нет на Стёпином компьютере. Шрифт автоматически заменился на какой-то другой, в котором не поддерживается символ
«/».
Теперь два числа, которые должны были быть разделены, слились в одно, и Стёпу это невероятно
расстраивает. Он подумал о том, что можно попробовать самому угадывать место, в котором должен
стоять символ «/», но потом понял, что в некоторых случаях подходящих вариантов может быть
несколько. Например, если на экране написано «1234», это может означать как то, что он находится
на 1 уровне из 234, так и то, что он находится на 12 уровне из 34.
Ему стало интересно, а сколько всего существует способов подставить символ «/» в надпись
на экране так, чтобы надпись была корректной, то есть чтобы слева и справа от символа были
корректные числа без лидирующих нулей и при этом левое число не превосходило правое. Помогите
Стёпе ответить на этот вопрос.
Формат входных данных
На вход подается одно целое число N — надпись на экране Стёпы (11 ⩽ N < 10100000).
Формат выходных данных
В выходной файл необходимо вывести одно целое число — количество способов подставить символ «/» в надпись на экране так, чтобы она была корректной. Гарантируется, что хотя бы один
такой способ существует