有一个 层的台阶，渡渡鸟现在正处于第 层。它一次可以跳一级台阶或两级台阶，问渡渡鸟到达第 层台阶一共有多少种不同的方案。由于方案数可能很大，你只需要输出其对 取模的值即可。
本题有多组测试，首先是一个整数 ，代表测试数据的组数。（）
之后 行，每行仅一个整数 （）。
输出 行，每行一个非负整数，代表这组测试方案数模 的值。
样例输入
5 0 1 2 100 1000000000000000000
样例输出
1 1 2 486534406 680023062
欢迎用各种神奇方式过掉这道签到题。