输入描述:

第一行输入一个整数，表示一共有组测试数据。
每组数据第一行输入一个字符串，第二行输入一个整数，表示一共有个询问。
接下来的行，每行输入一个整数，表示询问字符串的字典序第小的回文子串。

输出描述:

对于每一个询问输出一个答案，由于答案可能过大，你只需要输出这个子串对应的数对取模的结果。

备注:

。
组数据中的长度之和不超过100000。保证输入只含有数字1-9，不包含数字0
组数据中的和小于200000。
保证答案一定存在。