Aseer plays a simple game with DFS. In each turn, everyone tosses a coin. If the two coins are both face up or back up, no one will win the game. Otherwise, the one whose coin is face up get one score, and the other lose one score.
Aseer wants to know the expectation of the absolute value of his final score after t turns. But he is a little bit stupid, so he asks you to help him calculate the answer.
The first line of the input contains an integerT (T≤100)
Each of the next T lines describes a test case and contains one integer t (t≤10^5)
For
each test case, you should output an integer – the
expectation mod 10^9+7, which means, if the expectation equals to a/b, where a,b ∈
N and gcd(a,b) = 1, you
should output an natural number c<10^9+7, satisfying bc ≡a (mod 10^9+7).
2
1
5500000004
824218757