# Tribonacci

**Problem Statement**

We all know fibonnaci numbers.similarly we also have tribonnaci numbers whose first few terms is given as 0,1,1,2,4,7...

**Input**

First line of input contains T(number of test cases)

Next T lines contain a number N.

**Output**

For each test cases,output Nth tribonnaci number in a separate line.Since Nth term can be very large,output result modulo 1000000007

**Constraints**

T<=100

N<=10^10

**Sample Input**

```
```

5

1

2

3

4

5

**Sample Output**

```
```

0

1

1

2

4

*Problem Setter:Abhishek Sanghai*

**Languages:**C,C++,Java