Problem 42779. GJam March 2016 IOW: Polynesiaglot Large

This Challenge is derived from GJam March 2016 Annual I/O for Polynesiaglot. This is the Large input set. The max Qraw is 100^500, (V+C)^L.

The GJam story goes that words are such that consonants are always followed by a vowel. Determine the number of possible words of length L using C consonants and V vowels. The final Q is to be modulo of the prime 1E9+7.

Input: [C V L] , C[1,50], V[1,50], 1<=L<=500

Output: [Q] max Qraw is 100^500; Q=mod(Qraw,1E9+7)

Examples: [C V L] [Q]

[1 1 4] [5] {aaaa,aaba,abaa,baaa,baba}  invalid are {bbaa, aaab} 
[1 2 2] [6] {aa,ae,ba,be,ee,ea} invalid are {ab,eb,bb}

Google Code Jam 2016 Open Qualifier: April 8, 2016

Theory: This is a huge value problem, on the order of (C+V)^L, thus brute force will not work. This is also a probability tree type problem. Tree calculations can be reduced to a linear in L evaluation. Inspection shows Q(1)=V, Q(2)=V^2, L=3 Q(3)=V^3+V*C*V+C*V^2 = V*Q(L-1)+V*C*Q(L-2)+C*Q(L-1). There are no Cs at the Q1 level since can not end in a C. Qnext=f(Q(-1),Q(-2)). Qfinal=Q+C*Q(L-1)

Q3    V          C
Q2  V   C       V
Q1 V   V       V

One method to succeed in this problem is to use the java capability of Matlab. Cody Java Challenge. The primary reference sites are Java Math, Java BigDecimal, and Java BigInteger. The Java solution by the winner Stacy is included at the bottom of the test suite.