Шкільні часи

Limits: 3 sec., 512 MiB

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

• напишіть \(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\). І пам’ятайте, від перестановки множників послідовний добуток таки змінюється!

Input

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

Output

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

Constraints

\(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 балів: без додаткових обмежень.

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

Samples

Input (stdin) сopy	Output (stdout) сopy
2 1 1	3

Notes

У першому прикладі лише три рядки 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\).