Bob gets 2 bananas every day for n days. One of them is rotten while the other is fresh.

He feeds one of these bananas to his monkey. If the banana is rotten and the banana on the previous day was rotten too then the monkey gets very angry.

That is if he is fed rotten bananas on successive days, he gets angry and runs away. He doesn't mind rotten bananas otherwise.

Bob loves his monkey and doesn't wants to anger him. He wants to find the number of ways in which he can feed the monkey for n days while not making him angry. Help him.

Input

Input contains a number of test cases(T).

Each test case contains a single integer n denoting the total number of days, he has to feed the monkey.

1 <= T <= 10000

1 <= n <= 10¹⁵

Output

Output for each test case will be a single integer, the number of ways to feed the monkey without making him angry.

Since this number can be quite large print it modulo 10⁹+7.

Example

Input:
1
1

Output:
2

Description

Bob may feed either a rotten or a fresh banana. Thus he can feed him in 2 ways.