Dangerous Squares

All submissions for this problem are available.
A square of area $1$ unit square is given. It is divided into $4$ equal sections. The topleft section is colored in white whereas the remaining section is covered in black. It looks like this: ![Alt text](https://github.com/PratikLath/Images/blob/master/Image1.png?raw=true =150x150 "Initial state of the square") *Fig: Initial state of the square* In the initial state, the $current$ square refers to the topleft white colored section of the square drawn above. $K$ number of operations are required to be performed. There are basically $2$ types of operations. Both the operations have to be performed strictly in an alternating manner starting with the $1st$ operation i.e., if $K$ number of operations are performed, then the order in which operations are performed is : $1 > 2 > 1 > 2 > 1$………….….till $K$ times. The $2$ types of operations are: $1)$ Divide the $current$ square into $4$ equal parts. Color the top left part in black color and remaining portion in white color. After this operation, the top left part colored in black becomes the $current$ square. ![Alt text](https://github.com/PratikLath/Images/blob/master/Image2.png?raw=true=100... "After 1st operation") *Fig After 1st operation* $2)$ Divide the $current$ square into $4$ equal parts. Color the top left part in white color and remaining portion in black color. After this operation, the top left part colored in white becomes the $current$ square. ![Alt text](https://github.com/PratikLath/Images/blob/master/Image3.png?raw=true=125... "After 2nd operation") *Fig After 2nd operation* After performing $K$ operations, find the area of the white colored portion. The area can be represented in the form $P / Q$, where $P$ and $Q$ are coprime integers. Print $PQ^{1}$ modulo $1000000007$ (modulo refers to %) where $Q^{1}$ is the modulo inverse of $Q$. ###Input:  First line contains a single integer $T$ denoting the number of test cases.  Next $T$ lines contain a single integer $K$ denoting the number of operations required to be performed. ###Output: For the next $T$ lines, print a single integer denoting the answer to the test case in a separate line. ###Constraints  $1 \leq T \leq 10^5$  $0 \leq K \leq 10^{18}$ ###Subtasks  20 points : $0 \leq K \leq 15$  80 points : $Original Constraints$ ###Sample Input: 3 0 1 2 ###Sample Output: 250000002 687500005 828125006 ###EXPLANATION:  After $0$ operation, Area = 1/4.  After $1$ operation, Area = 3/16  After $2$ operations, Area = 13/64.Author:  pratiklath 
Tags  pratiklath 
Date Added:  23122019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 