There are 10 types of people - those understand binary and those who don't.

Every programmer has a soft spot for binary numbers in his/her heart. I being a programmer also had that soft spot until one fateful day. So what happened is that I, just like most of my programmer friends, was roaming around with a few of my friends chilling out a bit, minding my own business when a non-programmer guy came to me and put forward a question. The talk went on like this:

He: "Hey!"

Me: Hi

He: Do you know about binary numbers?

I was like 'Is he really asking me this question. Why won't I know about them.'

Me: Oh yeah, I do.

He: Thank god. Can you please solve this problem related to binary numbers?

Me: Why not.

I thought 'Huh! I could easily solve a question put forward by a non-programmer about binary numbers!'

He: So, you are given a number n. You need to find out the number of binary words of length n that has at least three zeroes between every two successive ones.

I was like 'What the hell. Did he really asked that.'

Me: I don't know how to do it. By I will try solving it.

He: Okay

From that day, I have been trying to solve that problem and more importantly I have been running away from him. I have devoted a large amount of time to solve it but all in vain. But now I feel is the time to put an end to the running. I come to you for my rescue. Don't let my love for binary numbers die. Please help me.

INPUT:

The first line contains t that denotes the number of test cases.
The next t lines contain an integer each. This integer is n.

OUTPUT:

For each test case output the number of binary words of length n that has at least three zeroes between every two successive ones. Since, the answer can be pretty big output ans mod (10^9 + 7)

CONSTRAINTS:

1 <= t <= 1000
1 <= n <= 100000