PIPI在玩一个凑数字的游戏。
游戏一开始，PIPI会得到n张纸牌，上面标有一个大小1~9的数字。
现在有Q次询问，每次给出一个正整数k，PIPI需要回答将这n张纸牌凑成k个数字后(一张牌只能用在一个数字中)，这个k个数字中最小值最大可以为多少？
例如给定3张纸牌，值为1,2,3，k=1时，凑一个321最大。k=2时，可以凑出12,3,显然3为答案。k=3时，只能凑出1,2,3,所以答案为1.
答案可能很大，请对1e9+7取模。

单组输入。
第一行两个整数n,q,1<=n,q<=1000000.
第二行给出长为n的字符串，其中每个字符表示每张纸牌上的数字。
接下来Q行，每行一个数字k，1<=k<=n.

输出Q行。
每次询问输出一个答案。

困难