---

Problem 658

---

Incomplete words II

In the context of formal languages, any finite sequence of letters of a given alphabet $\mathrm{\Sigma }$ is called a word over $\mathrm{\Sigma }$. We call a word incomplete if it does not contain every letter of $\mathrm{\Sigma }$.

For example, using the alphabet $\mathrm{\Sigma }=a,b,c$, ‘$ab$’, ‘$abab$’ and ‘ ‘ (the empty word) are incomplete words over $\mathrm{\Sigma }$, while ‘$abac$’ is a complete word over $\mathrm{\Sigma }$.

Given an alphabet $\mathrm{\Sigma }$ of $\alpha$ letters, we define $I(\alpha ,n)$ to be the number of incomplete words over $\mathrm{\Sigma }$ with a length not exceeding $n$.
For example, $I(3,0)=1$, $I(3,2)=13$ and $I(3,4)=79$.

Let $S(k,n)={\displaystyle \sum _{\alpha =1}^{k}I(\alpha ,n)}$.
For example, $S(4,4)=406$, $S(8,8)=27902680$ and $S(10,100)\equiv 983602076\text{ mod }1000000007$.

Find $S({10}^7,{10}^{12})$. Give your answer modulo $1000000007$.

---

不完整的单词II

在形式语言中，由给定字母表$\mathrm{\Sigma }$中的字母构成的有限序列被称为$\mathrm{\Sigma }$上的单词。如果一个单词不包含$\mathrm{\Sigma }$中的全部字母，我们称这个单词是不完整的。

例如，对于字母表$\mathrm{\Sigma }=a,b,c$，$\mathrm{\Sigma }$上的单词’$ab$’，’$ababa$’和’ ‘（空单词）都是不完整的，而’$abac$’则是完整的。

若字母表$\mathrm{\Sigma }$包含有$\alpha$个字母，我们记$I(\alpha ,n)$为$\mathrm{\Sigma }$上长度不超过$n$的不完整单词的数目。
例如，$I(3,0)=1$，$I(3,2)=13$，$I(3,4)=79$。

记$S(k,n)={\displaystyle \sum _{\alpha =1}^{k}I(\alpha ,n)}$。
例如，$S(4,4)=406$，$S(8,8)=27902680$，$S(10,100)\equiv 983602076\text{ mod }1000000007$。

求$S({10}^7,{10}^{12})$，并将你的答案对$1000000007$取余。

---