You are given a dice having six faces numbered as 1, 2, 3, 4, 5, and 6 respectively. You throw the dice \(n\) times and the outcomes are written serially in order to form an n-digit number. You are required to find the probability that the number formed is divisible by 11.

Input format

• The first line consists of a single integer \(T\) denoting the number of test cases
• Each of the next \(T\) lines contains a single integer \(n\) denoting the number of throws

Output format

The output must consist of \(T\) lines where each contains a single integer representing the required probability.

Print the answer modulo \(10^9+7\). If the answer is of the form \(\frac PQ\), then print \(PQ^{-1} (mod\ 10^9+7)\).

Constraints

\(1\le T\le 100\\1\le n \le 10^{18}\)