矩阵快速幂当然是签到题啦！
大家都知道斐波拉契数列的定义如下：
在大一时，大家都学过了矩阵，现在凤爪老师决定检验一下大家学习情况。凤爪老师写出了如下式子：
定义矩阵含义为 。
因为 ，所以 ，即：
当然最后一维是没必要的，可以写为：
这样就成功的更新了斐波那契数列，加上快速幂就可以达到快速求取的目的。当然，凤爪老师不想自己实现，所以他让你来负责完成。
现在给定 次询问，每次给出一个自然数 ，请你求出斐波那契数列的第 项的值，由于这个值可能很大，你需要对给出的 取模。
第一行包括一个正整数 ，表示测试的组数。
对于每组测试数据：
第一行输入两个整数 和 ，分别表示询问次数和模数。
接下来 行，每行输入一个自然数 ，表示一次询问。
对于每次询问，输出一行一个整数，表示 的值。
1 3 1000000007 0 1 10
0 1 55