众所周知,在所有数字中,数字4是一个比较不吉利的数字.因此,当 我们生成一些数字序列时,我们应该尽可能使我们生成的序列与4无关. 现在,你的任务是给出一个正整数n,计算出所有满足如下条件的正整 数:  这个数最多只包含n个数字.  这个数不包含4个连续的数字'4'.  这个数的数字数目不是任何一个大于10且数位上只有4的 数(即44444444444444...)的倍数.
只有一行,包含一个正整数n.
只有一行,包含一个非负整数,表示所求正整数的数目.由于这个数 可能很大,因此我们只需要输出这个数mod1000000007的值即可.