P10580 [蓝桥杯 2024 国 A] gcd 与 lcm

给定两个数 $x,y$，求有多少种不同的长度为 $n$ 的序列 $(a_1,a_2,\cdots,a_n)$，其所有元素的最大公约数为 $x$ 且最小公倍数为 $y$。 两个序列 $(a_1,a_2,\cdots,a_n)$ 与 $(b_1,b_2,\cdots,b_n)$ 不同，是指存在至少一个位置 $i$ 满足 $a_i\neq b_i$。 由于答案可能很大，请输出答案对 $998\ 244\ 353$ 取模后的结果。

无

无

对于 $40\%$ 的评测用例，$n\le 30$； 对于 $70\%$ 的评测用例，$n\le 5000$； 对于所有评测用例，$1\le Q\le 100$，$2\le n\le 10^5$，$1\le x,y\le 10^9$。