Elitedj is a famous hacker in the world. He usually likes to watch TV series on Tencent Video. Thereare annoying ads at the beginning of the video, only VIP users can skip the ads. As a hacker, Elitedjwants to execute an SQL command in Tencent’s database, the SQL command is UPDATE tencent_video_user_info SET isvip = true WHERE username = ’Elitedj’. But before doing this, Elitedj needs to get the root user password.

The Fibonacci sequence is very famous and its definition is as follows:

• f(n)=1, n \leq 2
• f(n)=f(n-1)+f(n-2), n>2

Now, we have a new function F(n), it represents the sum of the squares of the first n terms of the Fibonacci sequence. Its definition is as follows:

F(n)=\sum_{i=1}^{n}f(n)^2

There are n positive integers and the i−th integer is a_i. In order to get the root user password, Elitedj needs to answer the value of F(a_1), F(a_2), F(a_3), ..., F(a_n). You are a math enthusiast, canyou help him?

The first line contains a single integer n \ (1≤n≤10^4), indicating that there are n numbers.The nextnlines, each line contains an integer, representing a_1, a_2, a_3, ..., a_n \ (1≤a_1, a_2, a_3, ..., a_n ≤10^{18}).

For each a_i, print a single integer — the value of F(a_i). The answer may be very large so you needto modulo 10^9+ 7.