题目描述

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$ 表示答案。

3
25000000 2
20000000 17
114514 1919810

499122180 748683265
431089804 156793081
820514992 908533289

提示

【样例解释】

对于第一组数据，每步之前有 $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$。