John is attending a workshop for N days. He gets into trouble if he misses the workshop for two consecutive days.

Task

Determine the probability of him getting into trouble if he misses the workshop organized on the last day.

It can be shown that the probability can be represented as $\frac{P}{Q}$ where P and Q are coprime integers. Print the value of P*Q^-1 modulo 10⁹+7.

Note: There is an equal probability of John getting absent or present on any day.

Example

Assumption

• N = 2

Approach

• All possible combinations are (A,A) and (P,A) where P = Present , A = Absent.
• Out of these, only (A, A) gets john into trouble.
• The probability of this is 1/2. Thus the value of (1/2) modulo (10⁹+7) is 500000004.

Therefore the answer is 500000004.

Function description

Complete the absent function provided in the editor. This function takes the following parameter and returns the probability of John getting into trouble:

• N: Represents the number of days of the workshop

Input format

Note: This is the input format you must use to provide custom input (available above the Compile and Test button).

• The first line contains T denoting the number of test cases. T also specifies the number of times you have to run the absent function on a different set of inputs.
• For each test case:
  • The first line contains N denoting the number of days of the workshop

Output format

For each test case in a new line, print the required probability.

Constraints

$1 \leq T \leq10^5\\1 \leq N \leq 10^5$

Code snippets (also called starter code/boilerplate code) 

This question has code snippets for C, CPP, Java, and Python.