There is an Ant that lives in Baskerville and loves to travel. As Baskerville is a small place, it consists of only 5 cities placed one next to each other.

There is a train between each successive cities ie between City 1 - City 2, City 2 - City 3, ... City 5 - City 1. Note that our Ant loves to travel and gets happy after making exactly N train trips and returning back to home.
Ant lives in the city 1 from where she begins her journey. She asks you to find the number of ways she can make N train trips and come back to home.

Since the number of ways can be huge, print that number modulo 10^9 + 7.

Input
First line contains T, the number of test cases.
Then T lines follow.
Each line contains a single integer n, representing the number of train trips the ant needs to make.

Output
For each test case, print a single line containing the answer to the problem.

Constraints
1 <= T <= 1000
0 <= n <= 10^18