khann与快乐番薯（Hard Version)
TimeLimit:1000MS MemoryLimit:128MB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description
yh一看帅出的题这么简单，又把数列的范围增大了一下
你能帮khann解出这道题，让他顺利喝到奶茶嘛？
![1$S)D[PPR}DVWNQ9EB2{]26.gif](pic/upload/20220929/1664386771241014804.gif "1664386771241014804.gif")
还是这段数列！
1，1，2，3，5，8，13，21，34，55，89，144，233......
khann给你一个x，你输出数列的第x项就行！！
题意和上一题一样！但请注意本题X的范围！！
Tips：本题数据过大，结果是对1e9+7取模的（即取余 ， % ）
Input
第一行输入T，接下来有T组数据 1<=T<=5000
接下来T行，每行输入一个x ，代表khann想知道的数列的第几项
（1<=x<=1000000)
Output
对于每次输入的x，输出对应的数列的值
SampleInput
3 1 3 5
SampleOutput
1 2 5