Задача G. Марсианская арифметика: декомпозиция

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Марсианские правила для сложения натуральных чисел отличаются от земных.

Например, сумма 95238 + 276 вычисляется следующим образом:

+95238
276
9541014

Дано марсианское число A, требуется написать программу, вычисляющую количество способов разложить A на два неотрицательных слагаемых.

Разложения, отличающиеся порядком различных слагаемых, считаются различными.

Формат входного файла

Входной файл содержит единственное число — A.

Формат выходного файла

Выходной файл должен содержать единственное число — количество способов разложить число A на два слагаемых по модулю 108 + 7.

(Иными словами, поскольку ответ может быть большим, следует вывести остаток от его деления на 108 + 7).

Ограничения

0 ≤ A ≤ 101000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
23
12
2
123
52

0.036s 0.007s 15