唯一特征的命中期望¶

时间限制：0.5 秒；内存限制：128 MiB。时限按目标环境标准程序最慢中位数乘2，向上取整至0.5秒；见评测环境。

背景故事¶

档案馆用短标签定位一份长记录。每次随机抽取一种标签，只有标签在记录中恰好出现一次时，定位才成功。管理员想估计完成指定次数的成功定位需要尝试多少次。

(本故事由GPT-6重写)

给定长度为 \(n\) 的字符串 \(S\) .每次尝试都在 \(S\) 的本质不同的非空连续子串中等概率选择一个；各次尝试独立，允许重复选到同一个子串。选择的是不同字符串，不是位置区间。

如果选中的子串在 \(S\) 中恰好出现一次，这次尝试成功；否则失败。统计出现次数时允许重叠。对于每个询问 \(N\) ，求成功次数首次达到 \(N\) 时已经进行的尝试总数的期望。\(N=0\) 时为零。

令 \(P=1000000007\) .把精确期望写成最简非负分数 \(A/B\) ，其中 \(B>0\) .若 \(B\) 能被 \(P\) 整除，输出 \(-1\) ；否则输出 \(AB^{-1}\bmod P\) 的最小非负余数。

第一行 n Q .第二行包含长度为 \(n\) 的字符串 \(S\) ，每个字符的ASCII码都在33至126之间。接下来 \(Q\) 行，每行一个非负整数 \(N\) .

每个询问输出一行，按上述最简分数规则输出模值或 \(-1\) .

5 3
ababa
4
1
0

9
250000004
0

4 3
aaaa
1
4
1000000000000000000

4
16
196

3 3
a!a
1
2
4

250000003
500000006
5

样例1共有9种不同子串，其中恰好出现一次的四种是 bab 、abab 、baba 、ababa .单次成功率为 \(4/9\) ，取得4次成功的期望为9。

示意图

字符串 ababa 的9种不同子串；加框的4种只出现一次。

\(1\le n\le10^5\) ，\(1\le Q\le500\) ，\(0\le N\le10^{18}\) .字符集为ASCII码33至126的全部94个字符，不含空白。

Codex（GPT-6）重新设计：明确完整字符集、独立抽样及期望含义，并补全约分后分母不可逆时的输出规则。

共10个测试点，每点占10%；完整配方见测试说明。