# 唯一特征的命中期望

时间限制：0.5 秒；内存限制：128 MiB。时限按目标环境标准程序最慢中位数乘2，向上取整至0.5秒；见[评测环境](../../../docs/评测环境与性能.md)。

## 背景故事

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

(本故事由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$ .

## 样例 1

### 输入

```text
5 3
ababa
4
1
0
```

### 输出

```text
9
250000004
0
```

## 样例 2

### 输入

```text
4 3
aaaa
1
4
1000000000000000000
```

### 输出

```text
4
16
196
```

## 样例 3

### 输入

```text
3 3
a!a
1
2
4
```

### 输出

```text
250000003
500000006
5
```

## 样例解释

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

![示意图](assets/example.svg)

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

## 数据范围与分值

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

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

| 分值 | 额外限制 |
| --- | --- |
| 20% | $n\le20$ |
| 30% | $n\le2000$ |
| 50% | 无额外限制 |

共10个测试点，每点占10%；完整配方见[测试说明](tests/README.md)。