This Challenge is derived from GJam March 2016 Annual I/O for Polynesiaglot. This is a subset of small set 2. The max Qraw is 2^50 (<1.1259e15) for C[1,50], V[1,50], L[1,15].

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<=15

Output: [Q] max Qraw is 2^50 (<1.1259e15); 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 large 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(-1)

Q3    V          C
Q2  V   C       V
Q1 V   V       V

 This medium challenge has eps(Qraw) <0.25 so normal matlab doubles work. For the unbounded case a solution method is to convert this Challenge algorithm to Matlab BigInteger java calls. Solution sizes are on the order of (C+V)^L with the large case being C=50,V=50,L=500.