在形式语言的上下文中,给定字母表Σ的任何 字母有限序列被称为Σ上的单词。 我们称不包含Σ的每个字母的单词为不完整的单词。
例如,使用字母表Σ= {a,b,c},'ab','abab'和''(空 单词)是Σ上的不完整单词,而'abac'是Σ上的完整单词。
给定一个包含α个字母的字母表Σ,我们将I(α,n)定义为 Σ上长度不超过n的不完整的单词数量。 例如,I(3,0)= 1,I(3,2)= 13,I(3,4)= 79。

令S(k,n) = ∑ α=1kI(α,n) ,例如, S(4,4) = 406,S(8,8) = 27902680 , S(10,100) ≡ 983602076 mod 1000000007
求S( 107, 1012)。 给您的答案取模1000000007 。