- All Contests
- ProjectEuler+
- Project Euler #137: Fibonacci golden nuggets

# Project Euler #137: Fibonacci golden nuggets

# Project Euler #137: Fibonacci golden nuggets

_{This problem is a programming version of Problem 137 from projecteuler.net}

Consider the infinite polynomial series , where is the term in the Fibonacci sequence: ; that is, , and .

For this problem we shall be interested in values of for which is a positive integer.

Surprisingly

The corresponding values of for the first five natural numbers are shown below.

We shall call a golden nugget if is rational, because they become increasingly rarer; for example, the golden nugget is .

Given , find the golden nugget. Since this number can be very large, output it modulo .

**Input Format**

The first line of input contains , the number of test cases.

Each test case consists of a single line containing a single integer, .

**Constraints**

In the first test case:

In the second test case:

In the third test case:

**Output Format**

For each test case, output a single line containing a single integer, the answer for that test case.

**Sample Input**

```
2
1
10
```

**Sample Output**

```
2
74049690
```