Runes nòrdiques (2) P94319

Excavacions recents han descobert una antiga llengua nòrdica ja extincta. A partir de les runes trobades, s’ha deduït que hi havia $v$ vocals i $c$ consonants, i que se’n podien formar totes les paraules, amb dues excepcions:

• No hi podia haver dues o més vocals consecutives.

• Cada paraula havia de contenir almenys una vocal.

Per exemple, amb les dues vocals a i e i la consonant b es podien formar 10 paraules amb tres lletres: aba, abb, abe, bab, bba, bbe, beb, eba, ebb, ebe.

Quantes paraules amb $n$ lletres es podien formar amb $v$ vocals i $c$ consonants?

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$, $v$ i $c$. Assumiu $1 \le n \le 10^5$ i $1 \le v, c \le 1000$.

Sortida

Per a cada cas, escriviu quantes paraules de longitud $n$ es poden construir amb $v$ vocals i $c$ consonants. Com que els nombres poden ser molt grossos, feu els càlculs mòdul $10^9 + 7$.

Pista

Segons com sigui la vostra solució, recordeu que cal anar amb compte en restar dos nombres mòdul un tercer nombre.