其实只有三个部分：
- 环的 EGF：\(\frac{1}{2}\sum\limits_{i\geq 2}\frac{x^iy^i}{i}=\frac{1}{2}\left(\ln\frac{1}{1-xy}-xy\right)\) 。
- 链的 EGF：\(\frac{1}{2}\frac{xy^2}{1-xy}\) 。
- 点的 EGF：\(y\) 。
于是答案为：
\[\begin{aligned} ans&={}[x^n][y^m]\exp\left(\frac{1}{2}\left(\ln\frac{1}{1-xy}-xy\right)+\frac{1}{2}\frac{xy^2}{1-xy}+y\right)\\ &={}[s^n][t^{m-n}]\exp\left(\frac{1}{2}\ln\frac{1}{1-s}\right)\exp\left(-\frac{1}{2}s\right)\exp\left(\frac{1}{2}\frac{st}{1-s}+t\right)\\ &={}[s^n][t^{m-n}]\frac{1}{\sqrt{1-s}}e^{-s/2}\exp\left(\frac{1}{2}\frac{st}{1-s}+t\right)\\ &={}[s^n]\frac{1}{\sqrt{1-s}}e^{-s/2}[t^{m-n}]e^t\sum_{i\geq 0}\frac{1}{i!}\left(\frac{1}{2}\frac{st}{1-s}\right)^i\\ &={}[s^n]\frac{1}{\sqrt{1-s}}e^{-s/2}\sum_{0\leq i\leq m-n}\frac{1}{i!(n-m-i)!}\left(\frac{1}{2}\frac{s}{1-s}\right)^i\\ &={}[s^n]\frac{1}{\sqrt{1-s}}e^{-s/2}\frac{1}{(m-n)!}\left(\frac{2-s}{2-2s}\right)^{m-n}\\ \end{aligned} \]记 \(F_1=\frac{1}{\sqrt{1-s}},F_2=e^{-s/2},F_3=\left(\frac{2-s}{2-2s}\right)^{m-n}\) 。三者都是 D-finite 的，因此 \(F=\frac{1}{\sqrt{1-s}}e^{-s/2}\left(\frac{2-s}{2-2s}\right)^{m-n}\) 是 D-finite 的。
拆成两个部分：第一部分是 \(F_1F_2\)，我们的任务是解决 \(e^{-s/2}\sqrt{1-s}\) 。第二部分是 \(F_3\) ：
- Part 1：重定义 \(F_1\) 为 \(\sqrt{1-s}\)，记 \(F=F_1 F_2\) 。\(F'=F_1'F_2+F_1F_2'\)，其中 \(F_1'=\frac{1}{2\sqrt{1-x}}\)，于是 \(F'=\frac{1}{2\sqrt{1-s}}e^{-s/2}-\frac{1}{2}e^{-s/2}\sqrt{1-s}\) 。即 \((1-s)2F'=sF\) 。对比系数发现 \([s^i](1-s)2F'=2(i+1)F_{i+1}-2iF_i,[s^i]sF=F_{i-1}\) 。即 \(2(i+1)F_{i+1}=F_{i-1}+2iF_i\)，递推即可，初值 \(F_0=1,F_1=0\) 。
- Part 2：考虑令 \(G(x)=x^{m-n}\)。有 \(G'(x)=(m-n)x^{m-n-1}\)，故 \((m-n)G(x)-xG'(x)=0\) 。带入 \(F=\frac{2-s}{2-2s}\) 有 \((m-n)G(F)-F\frac{[G(F)]'}{F'}=0\) 。即 \((m-n)G(F)=(2-3s+s^2)[G(F)]'\)，对比系数递推即可。
时间复杂度 \(O(n+\log p)\) 。
signed main () {
IN (n), IN (m);
inv[1] = 1;
lep (i, 2, n) inv[i] = mul (mod - mod / i, inv[mod % i]);
f[0] = 1, f[1] = 0;
lep (i, 1, n - 1) f[i + 1] = mul (mul (inv2, inv[i + 1]), add (f[i - 1], mul (mul (2, i), f[i])));
const int rec = (m - n) % mod;
g[0] = 1, g[1] = mul (rec, inv2);
lep (i, 1, n - 1) g[i + 1] = mul (mul (inv2, inv[i + 1]), dec (mul (add (rec, 3 * i), g[i]), mul (i - 1, g[i - 1])));
int ret = 0;
lep (i, 0, n) pls (ret, mul (f[i], g[n - i]));
lep (i, 2, n) ret = mul (ret, i); // n !
lep (i, 1, n) ret = mul (ret, (m - i + 1) % mod); // m ! / (m - n) !
printf ("%d\n", ret);
return 0;
}