提示: 欢迎访问OurACM平台。
Problem 2117 特殊的数

Accept: 138    Submit: 474
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

一个由n位数字组成的数,它的每一位数字都是奇数,这样的n位数有多少个?

为了增加难度,Jason要求数字7和9只能出现偶数次。

Input

输入数据的第一行一个数T,表示输入数据的组数。

每组数据只有一个数n,表示一个数由n位数组成。

约定:

1≤T≤10000

1≤n≤10^18

Output

对于每组给定的输入,输出一行仅含一个数,满足以上条件的n位数的个数,由于答案可能很大,对1,000,000,007取模。

Sample Input

1 2

Sample Output

11

Source

FOJ有奖月赛-2013年4月(校赛热身赛)

Submit  Back  Status  Discuss