Moisil++ 2023 Clasa a 10a Mirror | ABC

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$.