自己独立做出来的，很激动。
【HT-093-Rainbow】G - 高中生数学题。
这里为了避免使用 \(x\)，将题面中的 \(x\) 写成 \(t\)。
这个形式很像多项式乘法的系数，用生成函数表示答案：
\[[x^n]\left(\sum_{j=0}^{+\infty}\sin(jt)x^j\right)^m
\]
（由于 \(\sin0=0\) 所以可以将求和下界改为 \(0\)。）
一个很典的转换就是注意到：
\[e^{ix}=\cos x+i\sin x \\
\sin x=\Im e^{ix}
\]
那么答案就可以改成：
\[\begin{aligned}
[x^n]\left(\sum_{j=0}^{\infty}\Im e^{ijt}x^j\right)^m&=[x^n]\left(\Im\sum_{j=0}^{\infty}(e^{it}x)^j\right)^m \\
&=[x^n]\left(\Im\frac{1}{1-e^{it}x}\right)^m
\end{aligned}
\]
欸，这个求 \(\Im\) 好像不能移到次方外面。那这样就只能暴力快速幂 + 多项式求逆计算了，可以过 \(n\) 比较小的点。
我们再想一想怎么算，回顾一下这个式子。
\[e^{ix}=\cos x+i\sin x
\]
我们发现我们好算的是：
\[\sin\left(\sum_{j=1}^m k_jt\right)
\]
而不是：
\[\prod_{j=1}^m\sin(k_jt)
\]
这两个式子什么关系？这两个式子让我们联想到积化和差公式，只要我们能将 \(\sin\) 函数的积转换为 \(\sin\) 函数的和，一切都好做了。
多角积化和差的式子是这样的：
\[\prod_{j=1}^m\sin(k_jt)=\left\{
\begin{aligned}
&\pm\frac 1{2^m}\sum_{\forall i,a_i\in\{0,1\}}(-1)^{\sum_{j=1}^m a_j}\sin\left(\sum_{j=1}^m(-1)^{a_j}k_jt\right),m\text{ is odd}\\
&\pm\frac 1{2^m}\sum_{\forall i,a_i\in\{0,1\}}(-1)^{\sum_{j=1}^m a_j}\cos\left(\sum_{j=1}^m(-1)^{a_j}k_jt\right),m\text{ is even}
\end{aligned}
\right.
\]
（写正负号的原因是我没用弄清楚怎样取正、取负）
用数学归纳法容易证明。
这两个式子差不多，先只考虑 \(m\) 是奇数的情况。将 \(\sin\) 改为指数的形式：
\[\begin{aligned}
\prod_{j=1}^m\sin(k_jt)&=\pm\frac 1{2^m}\sum_{\forall i,a_i\in\{0,1\}}(-1)^{\sum_{j=1}^m a_j}\sin\left(\sum_{j=1}^m(-1)^{a_j}k_jt\right) \\
&=\pm\frac 1{2^m}\Im\sum_{\forall i,a_i\in\{0,1\}}\prod_{j=1}^m(-1)^{a_j}e^{(-1)^{a_j}k_jt} \\
&=\pm\frac 1{2^m}\Im\prod_{j=1}^m(e^{k_jt}-e^{-k_jt})
\end{aligned}
\]
（这里求的是复数相加的复数，所以可以将 \(\Im\) 提出）
这个时候再将答案写成生成函数的形式，应该就长这样：
\[\begin{aligned}
[x^n]\pm\frac 1{2^m}\Im\left(\sum_{j=1}^m(e^{jt}-e^{-jt})\right)^m&=[x^n]\pm\frac 1{2^m}\Im\left(\frac 1{1-e^tx}-\frac 1{1-e^{-t}x}\right)^m \\
&=\pm\Im{\left(\frac{e^t-e^{-t}}{2}\right)^m}[x^{n-m}]\frac 1{(1-(e^t+e^{-t})x+x^2)^m}
\end{aligned}
\]
到了最后其实生成函数内部都变成了实数，所以不需要维护虚数域，这样可以减少常数。
多项式快速幂 + Bostan-Mori 求解分式远程系数即可。
#include <bits/stdc++.h>using namespace std;const int kM = 1e9 + 7;int T, n, m, x, y;int Fpow(int a, int b, int p, int r = 1) {for (; b; a = 1LL * a * a % p, b >>= 1) {if (b & 1) r = 1LL * r * a % p;}return r % p;
}vector<int> operator*(vector<int> &a, vector<int> &b) {vector<int> c(a.size() + b.size() - 1);for (int i = 0; i < a.size(); i++) {for (int j = 0; j < b.size(); j++) {c[i + j] = (c[i + j] + 1LL * a[i] * b[j]) % kM;}}return c;
}vector<int> Fpow(vector<int> a, int b, vector<int> r = {1}) {for (; b; a = a * a, b >>= 1) {if (b & 1) r = r * a;}return r;
}int BostanMori(int n, vector<int> f, vector<int> g) {for (int i; n; n >>= 1) {vector<int> h = g;for (int i = 0; i < h.size(); i++) {h[i] = i % 2 ? g[i] == 0 ? 0 : kM - g[i] : g[i];}f = f * h, g = g * h;for (i = n % 2; i < f.size(); i += 2) f[i / 2] = f[i];f.resize(i / 2);for (i = 0; i < g.size(); i += 2) g[i / 2] = g[i];g.resize(i / 2);}if (!f.size()) return 0;return 1LL * f[0] * Fpow(g[0], kM - 2, kM) % kM;
}int main() {ios::sync_with_stdio(0), cin.tie(0);for (cin >> T; T; T--) {cin >> n >> m >> y >> x;cout << BostanMori(n - m, {Fpow(y, m, kM)}, Fpow({1, (kM - 2 * x % kM) % kM, 1}, m)) << '\n';}return 0;
}