Srm444 avoidfour

众所周知，在所有数字中，数字 $4$ 是一个比较不吉利的数字。因此，当我们生成一些数字序列时，我们应该尽可能使我们生成的序列与 $4$ 无关。

现在，你的任务是给出一个正整数 $n$，计算出满足如下条件的正整数的个数：

• 这个数最多只包含 $n$ 个数字（即位数不超过 $n$）；
• 这个数不包含 $4$ 个连续的数字 4；
• 这个数的位数不是任何一个大于 $10$ 且各个数位上都只有 $4$ 的数（即 $44, 444, 4444, 44444, \ldots$）的倍数。

输入格式

只有一行，包含一个正整数 $n$。

输出格式

只有一行，包含一个非负整数，表示所求正整数的数目。由于这个数可能很大，因此我们只需要输出这个数对 $10^9+7$ 取模的值即可。

样例输入

8

样例输出

99953999

数据范围

• 对于 $30\%$ 的数据，$n\le 1000$；
• 对于 $100\%$ 的数据，$n\le 4\times 10^{10}$。

来源与许可

本题为 TopCoder SRM 444 试题「avoidfour」，题面与测试数据整理自 BZOJ 1894。

样例 1

输入

8

输出

99953999