老yd与并查集¶
预估时间限制：2 秒。内存限制：512 MB。
实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(4\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
本题采用倍率四，为单逆元表方案在完整范围内保留至少两倍实测余量；主方案与低内存方案的比较见题解。
背景故事¶
“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\) ，在非负实数上定义函数
这里 \(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¶
输入¶
1 3 7 4
5
3
10
137
65
38
输出¶
11
10153081
399262231
911840238
777440793
样例 2¶
输入¶
2 5 1 1
2
5
6
输出¶
4
6
样例 3¶
输入¶
1000000000 10000000 1000000000 1000000000
1
10000000
输出¶
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% | 无额外条件 |