QQ向来对排列问题很感兴趣。什么全排列呀，置换群呀，都是QQ曾经研究过的问题。现在，一般难度的排列问题已经难不倒QQ了，QQ想要更高程度的挑战。于是QQ经常找全全和样样切磋很多高难度的题目。全全和样样都是研究排列的百年难得一遇的奇才，对此也是乐此不疲哦。
最近，他们发现他们三个人的昵称居然都是由重复的字组成的。这个可是一个很有趣的现象呀。于是，QQ的奇思妙想又出来了，他们每个人的昵称的字都提取出来，这样就获得了Q，全，样这三个字，他希望用这三个字重新组成新的昵称，每个字都可以用无限次，当然这样的昵称很可能很难听。 QQ又在这些排列上加了一个附加的条件，就是Q这个字母不能连续出现两次。
比如说，我们令Hn表示当昵称由n个字组成时，问有多少个符合条件的昵称。
例如：
H1=3，具体方案：Q，样，全
H2=8，具体方案：Q样，Q全，样Q，样全，样样，全Q，全样，全全
再令Sn=H1+H2+…+Hn-1+Hn;
QQ的问题出来了，他想知道Sn，但是这个Sn有可能太大了，所以QQ只想知道这个Sn对9937取余的结果。
