A dice string | Practice Problems

A dice string

★★★★★

3.7

3 votes

Dynamic Programming, Matrix, Probability spaces, Algorithms, Probablity, Modular exponentiation

Details

Submissions

Discussion

Editorial

Problem

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}$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

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.