题⽬描述(Description)

⼩G最近发现了⼀种⾮常有趣的数，他将这种数称之为Sam数。Sam数具有以下特征：相邻两位的数字之差不超过2。⼩G还将Sam数按位数进⾏了分类，他将⼀个k位Sam数称之为k阶Sam数。但不幸的是⼩G 发现他数不清第k阶的Sam数⼀共有多少个，这个时候机智的他想到了向你求助

输⼊格式(Format Input)

第⼀⾏为⼀个整数k，含义⻅题⾯。

⼀⾏⼀个整数ans，表示k阶的Sam数的个数。由于第k阶Sam数⾮常多，你只需要输出ans mod 1,000,000,007。

时间限制(Time Limit): 300 ms

内存限制(Memory Limit): 65536 KB

0本身是Sam数，其它数字没有前导零！