Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

A+B

(Время: 1 сек. Память: 32 Мб Сложность: 66%)

Рассмотрим a, b и c – целые неотрицательные числа, записанные в десятичной системе счисления. Пусть они имеют одинаковую длину n, при этом запись может начинаться с нуля. Числа записаны одно под другим, цифры расположены в три строки и n столбцов. Рассмотрим пример такой записи:

01211
12099
23300

Требуется переставить столбцы в этой записи таким образом, чтобы выполнялось равенство a + b = c. В полученной записи ведущие нули уже запрещены. Сколько существует различных способов это сделать?

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

Поскольку ответ может быть довольно большим, требуется посчитать для него остаток по модулю 109 + 7.

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

Входной файл INPUT.TXT содержит целые неотрицательные числа a, b и c по одному в строке. Каждое число состоит из n десятичных цифр и может начинаться с нуля (2 ≤ n ≤ 2×105).

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

В выходной файл OUTPUT.TXT выведите количество подходящих перестановок столбцов по модулю 109 + 7.

Примеры

INPUT.TXTOUTPUT.TXT
1123
123
246
6
201
02
03
1
301211
12099
23300
4
4121
214
999
0

Пояснения к примерам

В первом примере подходят все перестановки столбцов.

Во втором примере единственная подходящая перестановка – 10 + 20 = 30. 01 + 02 = 03 не считается из-за наличия ведущих нулей.

В третьем примере возможны варианты 10121 + 21909 = 32030 и 12101 + 20919 = 33020, причём каждый из них может быть получен двумя разными перестановками.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 A. Два станка
 B. Разбиение таблицы
 C. Изменённая ДНК
 D. Антенна
 E. Календарь на Альфе Центавра
 F. Числа
 G. Хорошие раскраски
 H. A+B

Красноярский краевой Дворец пионеров, (c)2006 - 2021, E-mail: admin@acmp.ru