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
In first case, ant has to make 0 trips. So the ant stays at city 1 and has only 1 option.
In second case, ant has to make 3 trips. No matter what combination we try, we can never reach back to city 1 back after 3 trips. So answer is 0.
In third case, ant makes 4 trips. There are 6 ways in which it can reach back to city 1.
Way 1: 1-->2-->1-->2-->1
Way 2: 1-->2-->3-->2-->1
Way 3: 1-->5-->1-->5-->1
Way 4: 1-->5-->4-->5-->1
Way 5: 1-->5-->1-->2-->1
Way 6: 1-->2-->1-->5-->1
