Srm444 avoidfour
时间限制：1s 空间限制：64MB
题目描述
众所周知，在所有数字中，数字4是一个比较不吉利的数字。因此，当 我们生成一些数字序列时，我们应该尽可能使我们生成的序列与4无关。 现在，你的任务是给出一个正整数n，计算出所有满足如下条件的正整 数： 这个数最多只包含n个数字。 这个数不包含4个连续的数字'4'。 这个数的数字数目不是任何一个大于10且数位上只有4的 数(即44,444,4444,44444...)的倍数。
输入格式
只有一行，包含一个正整数n。
输出格式
只有一行，包含一个非负整数，表示所求正整数的数目。由于这个数 可能很大，因此我们只需要输出这个数mod1000000007的值即可。
样例输入
8
样例输出
99953999
提示
对于30%的数据，n 6 1000; 对于100%的数据，n 6 40000000000。
题目来源
没有写明来源