题目描述

古老的数字神庙里保存着神秘的密码。这些由数字组成的序列蕴藏着力量。每位守护者都要确保密码中任意连续三个字符组成的部分都是好的，只有这样，数字的能量才能保持稳定。

由三个数字组成的密码 $(x,y,z)$ 被称为好的，当且仅当满足以下两个条件：

• 三个数字之和不小于 $10$。
• 三个数字的乘积能被 $24$ 整除。

大祭司想构造一个长度为 $n$ 的密码，使其中每三个相邻的数字都组成好的三元组。只有这样的密码才是神圣的，才能被刻在神庙的墙上。当然，第一位数字不能是 $0$：神圣的文字不能以空无开头。

你的任务是计算长度为 $n$ 的密码一共有多少个。密码使用十进制数字 $0$ 至 $9$；除第一位外，其余位置可以是 $0$。

输入格式

输入仅一行，包含一个整数 $n$，表示这个数的位数，满足 $3\le n\le 5\times10^5$。

输出格式

输出一个整数，表示长度为 $n$、每三个连续数字均组成好三元组的数的数量，对 $10^9+7$ 取模。

3

277

215

929081963