SP13745 SAFECRAC - Crack the Safe

Johnny（已经不再是小孩子了）是一名超级特工。他正在追踪一群世界上最危险的恐怖分子。他的情报显示，一名恐怖分子藏身于一家豪华酒店中。阻挡 Johnny 的唯一障碍是房间入口处的安全门。 安全门的锁看起来是这样的： ``` 1 2 3 4 5 6 7 8 9 0 Enter ``` 需要注意的是，Enter 键不能作为密码的一部分。 经过一番侦查，Johnny 发现密码中每一对相邻的数字在键盘上都是相邻位置。相邻的定义是，这两个数字在键盘上共享一条公共边。 现在，Johnny 想知道密码有多少种不同的可能性，以便他可以配置一台电脑来破解这个锁。 **输入格式：** 第一行输入一个整数 $T$，表示测试用例的数量。接下来有 $T$ 行，每行包含一个整数 $N$，表示密码的长度。 **输出格式：** 对于每个测试用例，输出不同密码的可能性数量。由于结果可能非常大，请输出结果对 $1000000007$ 取模后的值。 **数据范围与提示：** $1 \le T \le 1,000$， $1 \le N \le 100,000$。 **样例输入：** ``` 2 3 25 ``` **样例输出：** ``` 74 478325846 ``` **本翻译由 AI 自动生成**

无

无