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

Условие

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

• Аргументы записываются в десятичной системе счисления.
• Производится поразрядное сложение цифр справа налево.
• В случае, если сумма цифр превысила 9, разряд переноса не прибавляется к следующему, а вставляется в результат перед текущим разрядом.

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

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

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

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

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

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

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

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

Ограничения

0 ≤ A ≤ 10¹⁰⁰⁰

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

23

12

123

52