Fractals are special geometric shape that have following properties:

1. Finite area

2. Infinite perimeter

SnowFlake is a one of them.

 your task is to find no. of vertices in snowflake after N iterations starting with equilateral triangle.

for explanation first 4 iterations are given in following figure:-

 

Input:

First line consists of Q (1<= Q <= 10^5) denotes no of test cases.

Each test case consist of single integer N (1<= N <= 10^18).

Output:

Single integer denoting no. of outward vertices in new line for each test case.

Note: answer can be very large print answer under modulo 10^9+7

Note: Copy and paste is disabled for all the questions. Try not to use other ides.