Cerință

Un string format din literele 'a', 'b' și 'c' este bun dacă nu există un 'a' și un 'b' care să se afle pe poziții consecutive.

De exemplu, aaaa, c și bcaacb sunt bune, pe când bac și acab nu sunt bune.

Câte stringuri bune care conțin $a$ de 'a', $b$ de 'b' și $c$ de 'c' există? Deoarece răspunsul poate fi foarte mare, afișați restul împărțirii acestuia la $10^9+7$.

Date de intrare

Pe prima linie a fișierului de intrare abc.in se vor afla trei numere $a$, $b$ și $c$.

Date de ieșire

Fișierul de ieșire abc.out va conține restul împărțirii la $10^9+7$ a numărului de stringuri bune care conțin $a$ de 'a', $b$ de 'b' și $c$ de 'c'.

Restricții și precizări

• $1 \le a,b,c \le 5 \cdot 10^5$;
• Pentru $5$ puncte, $c=1$;
• Pentru încă $20$ de puncte, $c=2$;
• Pentru încă $10$ puncte, $a,b,c \le 5$;
• Pentru încă $20$ de puncte, $a,b,c \le 100$;
• Pentru încă $15$ puncte, $a,b,c \le 2 \ 000$;
• Pentru restul de $30$ de puncte, nu se impun restricții suplimentare.

Exemplul 1

abc.in

1 1 2

abc.out

6

Explicație

Cele 6 stringuri bune sunt: acbc, accb, bcac, bcca, cacb și cbca.

Exemplul 2

abc.in

2 2 2

abc.out

12

Explicație

Cele 12 stringuri bune sunt: aacbbc, aacbcb, aaccbb, acacbb, acbbca, bbcaac, bbcaca, bbccaa, bcaacb, bcbcaa, caacbb și cbbcaa.

Exemplul 3

abc.in

21 35 29

abc.out

306014034

Explicație

Răspunsul trebuie afișat modulo $10^9+7$.