P14642 【OIMO Round 1】十二宫标志

X 喜欢在城市里随机游走，她为自己的游走方式制定了一个规则。 城市可以视作一个二维平面直角坐标系，初始 X 在 $(0,0)$ 位置，面朝的方向均匀随机。 X 会选定一个概率 $p$，并执行以下步骤 $n$ 次： - 有 $p$ 的概率，她会右转（即顺时针转向）$30\degree$（即 $\frac\pi6$ 弧度）；有 $1-p$ 的概率，她不会改变方向。 - 面朝现在的方向前进一个单位长度。 H 想要去找 X，但 X 刚刚结束一次游走，H 并不清楚她的位置。 H 在给 X 发消息前想要知道，X 在结束了一次游走后，与点 $(0,0)$ 间欧氏距离的平方的期望值是多少？ 容易证明，答案可以唯一地表示为 $a+b\sqrt 3$ 的形式（其中 $a,b$ 均为有理数）。请你输出 $a,b$ 对 $998244353$ 取模的值。

第一行一个正整数 $T$，表示有 $T$ 组数据。 接下来 $T$ 行，每行两个整数 $p',n$。其中 $p' = p\times 10^8$。

输出 $T$ 行，每行两个整数 $a,b$ 表示答案。

【样例解释】 对于第一组数据，每步之前有 $1/4$ 的概率转向，所以有： - $\frac9{16}$ 的概率直行两次，到原点距离的平方为 $4$； - $\frac3{16}$ 的概率在第一次转向，第二次不转，到原点距离的平方为 $4$； - $\frac3{16}$ 的概率在第一次不转，第二次转向，到原点距离的平方为 $(2+\sqrt 3)$； - $\frac1{16}$ 的概率转向两次，到原点距离的平方为 $(2+\sqrt 3)$。 根据以上情况，可以算出期望值为 $\frac72+\frac14\sqrt 3$。 对于第二组数据，答案为： $$\frac{20196247660583+6251719221244 \sqrt{3}}{152587890625}$$ **本题采用捆绑测试。** - Subtask 1（10 pts）：$1 \le T \le 100$，$1 \le n \le 18$； - Subtask 2（25 pts）：$1\le n \le 100$； - Subtask 3（25 pts）：$p'=5\times 10^7$，$1 \le n \le 10^5$； - Subtask 4（40 pts）：无特殊限制。 对于全部的数据，$1\leq T \leq 10^3$，$0 \leq p' \leq 10^8$，$1 \leq n \leq 10^7$。