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}\)
For n=1, possible outcomes are 1,2,3,4,5,6. Since none of these is divisible by 11, probability is 0.
For n=2, total number of possible outcomes are 36, out of which six ("11","22","33","44","55","66") are divisible by 11. So, probability is 1/6.
