---

Problem 873

---

Words with Gaps

Let $W(p,q,r)$ be the number of words that can be formed using the letter A $p$ times, the letter B $q$ times and the letter C $r$ times with the condition that every A is separated from every B by at least two Cs. For example, CACACCBB is a valid word for $W(2,2,4)$ but ACBCACBC is not.

You are given $W(2,2,4)=32$ and $W(4,4,44)=13908607644$.

Find $W(10^6,10^7,10^8)$. Give your answer modulo $1\ 000\ 000\ 007$.

---

带间隔的单词

记$W(p,q,r)$为由$p$个A、$q$个B和$r$个C构成、且任意A和B之间间隔至少两个C的单词数目。例如，对于$W(2,2,4)$，CACACCBB是一个合法单词，而ACBCACBC不是。

已知$W(2,2,4)=32$，$W(4,4,44)=13908607644$。

求$W(10^6,10^7,10^8)$, 并对$1\ 000\ 000\ 007$取余作为你的答案。

---