小d接到了一个布置会场的任务。
他需要将贵宾观众席的椅子排成一排，一共需要N个。
上级领导指示，他只能使用两种椅子。（A类型和B类型）并且假设每种椅子的数量都是无限的。
而其如果想要摆置一个B类型的椅子，对应就需要必须有连续两个一起布置。换句话说，就是如果出现了B类型的椅子，其必须且只有两个连着B类型的椅子。
小d突然想知道对应N个椅子排成一列，他能够有多少种布置的方式.
本题包含多组输入第一行输入一个整数t，表示测试数据的组数
每组测试数据包含一行，输入一个整数N，表示一共需要摆放的椅子数量
t<=1000
1<=N<=100000000000000000（10^18）
每组测试数据输出包含一行，表示一共有多少种布置的方式,方案数可能会很大，输出对1000000007取摸的结果。