adece

Cerința

Se dau $3$ numere $a$, $b$ și $c$.

Câte string-uri care conțin $a$ caractere 'a', $b$ caractere 'b' și $c$ caractere 'c' nu au niciun substring egal cu "abc"?

Deoarece răspunsul poate fi foarte mare, afișați-l modulo $100\,000\,007$.

Date de intrare

Pe prima linie a fișierului de intrare adece.in se vor afla $3$ numere $a$, $b$ și $c$ ($1 \le a,b,c \le 3000$) — cu semnificațiile din enunț.

Date de ieșire

Fișierul de ieșire adece.out va conține răspunsul problemei, modulo $100\,000\,007$.

Restricții și precizări

• Pentru 20 de puncte, $a,b,c \le 5$;
• Pentru 20 de puncte, $c=1$;
• Pentru 25 de puncte, $a,b,c \le 100$;
• Pentru 35 de puncte, nu se impun restricții suplimentare.
• Se garantează că modulul este prim.

Exemple

Exemplu 1:

adece.in

1 1 1

adece.out

5

Exemplu 2:

adece.in

1 1 2

adece.out

10

Exemplu 3:

adece.in

2 2 2

adece.out

67

Exemplu 4:

adece.in

69 69 69

adece.out

5545765

Explicații

• În primul exemplu, cele $5$ string-uri care respectă condițiile din enunț sunt: "acb", "bac", "bca", "cab" și "cba".
• În al doilea exemplu, cele $10$ string-uri care respectă condițiile din enunț sunt: "acbc", "accb", "bacc", "bcac", "bcca", "cacb", "cbac", "cbca" , "ccab" și "ccba".