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

printМарсианская арифметика: декомпозиция

Ограничения: время – 1s/2s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Марсианские правила для сложения натуральных чисел отличаются от земных.
  • Аргументы записываются в десятичной системе счисления.
  • Производится поразрядное сложение цифр справа налево.
  • В случае, если сумма цифр превысила 9, разряд переноса не прибавляется к следующему, а вставляется в результат перед текущим разрядом.
Например, сумма `95238\ +\ 276` вычисляется следующим образом:
9 5 2 3 8
    2 7 6
9 5 41014
Дано марсианское число `A`, требуется написать программу, вычисляющую количество способов разложить `A` на два неотрицательных слагаемых.
Разложения, отличающиеся порядком различных слагаемых, считаются различными.
Входной файл содержит единственное число – `A` (`0\ ≤\ A\ ≤\ 10^1000`).
Выходной файл должен содержать единственное число – количество способов разложить число `A` на два слагаемых по модулю `10^8\ +\ 7`. (Иными словами, поскольку ответ может быть большим, следует вывести остаток от его деления на `10^8\ +\ 7`).

Пример ввода 1

23

Пример вывода 1

12

Пример ввода 2

123

Пример вывода 2

52
Источник: http://imcs.dvgu.ru/cats/ Школьники ACM, 2010
loading