Шкільні часи

Обмеження: 3 сек., 512 МіБ

Працюючи з іноземними клієнтами Зеник згадав шкільні часи, коли на домашнє завдання вчителька англійської мови дала таке завдання:

• напишіть \(cnt_a\) разів літеру a,

• напишіть \(cnt_b\) разів літеру b,

• напишіть \(cnt_c\) разів літеру c.

Згадуючи школу, Зеник згадав також уроки алгебри, де він колись вигадав наступну операцію множення \(*\), яка працює лише із англійськими літерами a, b та c: добуток двох різних букв дає іншу третю букву, а добуток однакових дає ту ж літеру. Наприклад, \(a * a = a\), та \(b * c = c * b = a\).

Зеник вирішив зробити домашнє з англійської ще раз, але трішки ускладнити його алгеброю. Отже, він виписує всі потрібні букви в певному порядку, при цьому утворюючи рядок довжиною \(cnt_a + cnt_b + cnt_c\). Зауважте, що літери можуть бути виписані у довільному порядку.

Для отриманого рядка Зеник почав рахувати послідовний добуток усіх його символів. Послідовний добуток — це добуток усіх літер, де множення відбувається послідовно зліва направо. Добуток перших двох літер рядка дає в результаті одну літеру, яку ми помножимо на третю літеру, результат цього своєю чергою на четверту, і так далі.

Зенику стало цікаво, скільки різних рядків він міг виписати таких, що в результаті послідовного множення він отримає літеру \(c\). Виписані рядки вважатимемо різними тоді й лише тоді, коли існує позиція, в якій знаходяться різні символи. Зеник переживає, що кількість різних рядків може бути настільки великою, що він навіть не зрозуміє що це за число, тож він просить вас порахувати цю кількість по модулю простого числа \(10^9 + 7\). І пам’ятайте, від перестановки множників послідовний добуток таки змінюється!

Вхідні дані

У першому рядку задано три цілих числа \(cnt_a\), \(cnt_b\) та \(cnt_c\) — кількість відповідних символів у рядку.

Вихідні дані

Виведіть одне ціле число — остачу від ділення кількості різних шуканих рядків на простий модуль \(10^9 + 7\).

Обмеження

\(1 \le cnt_a + cnt_b + cnt_c \le 10^3\).

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 7 балів: \(cnt_a = cnt_b = 0\),

• 8 балів: \(cnt_a + cnt_b + cnt_c \le 9\),

• 24 балів: \(cnt_a, cnt_b, cnt_c \le 30\),

• 33 балів: \(cnt_a, cnt_b \le 74, cnt_c = 0\),

• 17 балів: \(cnt_a, cnt_b, cnt_c \le 74\),

• 10 балів: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 1 1	3

Примітки

У першому прикладі лише три рядки acba, aabc та caba підходять, оскільки:

\(a * c * b * a = b * b * a = b * a = c\),

\(a * a * b * c = a * b * c = c * c = c\),

\(c * a * b * a = b * b * a = b * a = c\).