定义一个无限长的数组，给定前n项，若in,则a[i]=a[i-n]。接下来有Q次询问，每次给定一个N,你只需回答对1e9+7取模的结果。

输入描述:

第一行输入n,Q 第二行输入n个数字表示a数组的前n项 接下来Q行，每行输入一个N表示一次询问。 1=a[i],n=3000000,1=Q=300000,1=N=1e18

输出描述:

每次询问，输出一个整数。