Молчун, Ворчун и Пилюлькин играют в карточную игру на троих. Правила игры следующие.
Сначала у каждого из трех игроков есть колода, состоящая из некоторого количества карт.
В колоде Пилюлькина N карт, в колоде Молчуна M карт, а в колоде Ворчуна K карт. На каждой карточке написана буква p, m или v. Порядок карт в колодах не может быть изменен. Игроки ходят по очереди. Пилюлькин ходит первым.
Если в колоде текущего игрока есть хотя бы одна карта, сбросьте верхнюю карту в колоде.
Затем следующий ход переходит к игроку, имя которого начинается с буквы на сброшенной карте.Например, если на карте написано «p», следующий ход переходит Пилюлькину.
Если колода текущего игрока пуста, игра заканчивается, и текущий игрок выигрывает игру.
Есть
3N + M + K возможных вариантов раскладки начальных колод трех игроков.
Сколько из этих шаблонов приведет к победе Пилюлькина? Поскольку ответ может быть большим, выведите его по модулю 1000000007 (= 10
9 +7).
Входные данные
На вход подается три целых числа N, M и K (2<=N, M, K <=3*10
5).
Выходные данные
Выведите количество победных для Пилюлькина шаблонов по модулю 1000000007 (= 10
9 +7).
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
1 1 1 |
17 |
Если карта Пилюлькина - p, то Пилюлькин выиграет независимо от карты Молчуна и Ворчуна. Таких вариантов 3 × 3 = 9.
Если карта Пилюлькина - m, Пилюлькин выиграет только тогда, когда карта Молчуна - p, или когда карта Молчуна - v, а карта Ворчуна - p. Всего таких шаблоно 3 + 1 = 4.
Если карта Пилюлькина - v, Пилюлькин выиграет только тогда, когда карта Ворчуна - p, или когда карта Ворчуна - m, а карта Ворчуна - p. Всего таких шаблонов 3 + 1 = 4.
Таким образом, всего 9 + 4 + 4 = 17 шаблонов, которые приведут к победе Пилюлькина. |
| 2 |
4 2 2 |
1227 |
|
| 3 |
1000 1000 1000 |
261790852 |
|