# 老yd与并查集

预估时间限制：2 秒。内存限制：512 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 $4$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

本题采用倍率四，为单逆元表方案在完整范围内保留至少两倍实测余量；主方案与低内存方案的比较见[题解](solution.zh.md)。

## 背景故事

> “parent的parent还是parent——路径压缩并查集”

老yd对并查集的深入研究令人折服：无论是关于路径压缩的伦理名言，还是对带权并查集的熟练运用，都颇有心得。于是，他发明了一个定义域为非负实数的函数 $f(x)$：小于 $B$ 时取常数 $A$；从 $B$ 开始，则由 $C f(x-1)+D f(x-e)$ 递推，其中 $e$ 是自然对数的底数。

他已经写出一个暴力程序，能够求出 $f(n)$ 对 $10^9+7$ 取模的结果。现在，他想请你写一份标程，验证他的暴力程序是否正确。他会提出 $M$ 次询问，请分别输出答案。

## 形式化问题描述

给定整数 $A,B,C,D$ ，在非负实数上定义函数

$$f(x)=\begin{cases}A,&0\le x<B,\\C f(x-1)+D f(x-e),&x\ge B.\end{cases}$$

这里 $e=\sum_{j=0}^{\infty}1/j!$ 是自然对数的底数，取其数学上的精确值。保证 $B\ge3>e$ ，因此递归涉及的参数始终非负；每条递归分支也会终止。

给出 $M$ 个整数询问 $n$ .对每个询问，求 $f(n)$ 对 $10^9+7$ 取模的非负最小剩余。各询问使用同一组 $A,B,C,D$ .

## 输入格式

第一行四个整数 $A,B,C,D$ .第二行一个整数 $M$ .接下来 $M$ 行，每行一个整数 $n$ .

## 输出格式

输出 $M$ 行，依次给出每个询问的模值。

## 样例

### 样例 1

### 输入

```text
1 3 7 4
5
3
10
137
65
38
```

### 输出

```text
11
10153081
399262231
911840238
777440793
```

### 样例 2

### 输入

```text
2 5 1 1
2
5
6
```

### 输出

```text
4
6
```

### 样例 3

### 输入

```text
1000000000 10000000 1000000000 1000000000
1
10000000
```

### 输出

```text
98
```

## 样例解释

第一组中 $f(3)=7f(2)+4f(3-e)=7+4=11$ .第二组中 $f(5)=4$ ，而 $f(6)=f(5)+f(6-e)=4+2=6$ .第三组只进行一次展开，其精确值为 $2\times10^{18}$ ，取模后为 $98$ .

## 数据范围与保证

$1\le A,C,D\le10^9$ , $3\le B\le n\le10^7$ , $1\le M\le5$ .

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |