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
3 0 3 4
1 0 6
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
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor