Пусть $W(p,q,r)$ будет количеством слов, которые возможно образовать, используя букву A $p$ раз, букву B $q$ раз и букву C $r$ раз, при условии, что каждая A отделена от каждой B как минимум двумя C. Например, CACACCBB является разрешенным словом для $W(2,2,4)$, в то время как ACBCACBC таковым не является.

Известно, что $W(2,2,4)=32$ и $W(4,4,44)=13908607644$.

Найдите $W(10^6,10^7,10^8)$. В качестве ответа приведите остаток от деления полученного числа на $1\,000\,000\,007$.