定义超级斐波那契数列如下：给定整数 ，该序列的前 项均为 ；对于 k" ，第 项为前 项之和，即 现给定整数 和查询次数 ，每次查询一个正整数 ，请输出该序列的第 项对 取模后的值。

输入描述:

第一行输入两个整数 ； 此后 行，每行输入一个正整数 。

输出描述:

输出 行，每行输出一个整数，表示对应查询的答案对 取模后的值。