410168: GYM103967 D Симметричные карты

D. Симметричные картыограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Как это изредка бывает, вся семья Смитов собралась вместе за столом после ужина, чтобы сыграть в карточную игру. В этой игре есть карточки, на каждой из которых написана какая-то цифра от 0 до $$$9$$$.

В какой-то момент (почти сразу) Рик сказал, что ему скучно, и ушел, забрав с собой Морти, и играть остались только Бет, Джерри и Саммер. Для очередной игры они решили каждый построить последовательность из $$$a$$$, $$$b$$$ и $$$c$$$ карточек, соответственно (назовем эти последовательности $$$A$$$, $$$B$$$ и $$$C$$$). Но чтобы игра получилась интересной, обязательно должны выполняться следующие условия:

• если выложить подряд последовательности $$$A$$$ и $$$B$$$ (именно в таком порядке) вместе, получившаяся последовательность должна читаться одинаково слева-направо и справа-налево;
• аналогично для последовательностей $$$A$$$ и $$$C$$$, их конкатенация должна быть палиндромом;
• и аналогично для последовательностей $$$B$$$ и $$$C$$$.

Чтобы не перестраивать много раз последовательности в поисках лучшего варианта, Смиты решили попросить вас общее количество последовательностей из карточек, удовлетворяющих условию, ведь самый умный в семье, Рик, явно не захочет этим заниматься.

Поскольку это число может быть очень большим, найдите его остаток по модулю числа $$$10^9 + 7$$$.

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

В первой и единственной строке ввода через пробел перечислены три целых числа $$$a$$$, $$$b$$$ и $$$c$$$ — длины последовательностей, которые хотят получить Бет, Джерри и Саммер, соответственно ($$$1 \leqslant a, b, c \leqslant 10^6$$$).

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

В единственной строке выведите целое число — количество возможных троек последовательностей карточек с длинами $$$a$$$, $$$b$$$, $$$c$$$, удовлетворяющих условию, по модулю $$$10^9 + 7$$$.

ПримерыВходные данные

2 3 4

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

100

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

101 102 103

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

193000119