Description

快乐是人类追求美好生活的动力源泉。

小明的快乐就是对着苹果树发呆，有一天，他在做 OI 题的时候想，我能不能对一个只有红色和棕色颜色的树，去定义这棵树上面有多少个红色的苹果。于是，他定义，对于一个节点只有棕红两种颜色的树，树上每一个红色的极大连通块就是一个苹果。

现在，小明十分开心的将后院的苹果树画了下来，准备数苹果个数，但是发现这棵树状态不是保持一致的，具体来说，每棵树有 $p$ 的概率是红色， $1-p$ 的概率是棕色，于是小明想要知道期望状态下有几个苹果，可惜小明的数学不太好，苹果树也太大，于是他来请求技术精湛的你来帮帮他。

输出 $\mod{998244353}$ 的答案，具体来说，$998244353$ 是一个质数，因此 $\forall x\text{不同余于} 0\mod 998244353$ ，都存在元素 $y$ ，使得 $x\cdot y\equiv 1$ ，称 $y$ 为 $x$ 的逆元，记作 $x^{-1}$，则在 $\mod{998244353}$ 意义下，$\frac{p}{q}$ 为 $p\cdot q^{-1}$ ，同理，输入中的 $p$ 也以这种形式表达。

样例解释：

1. 可以验证，每个点的概率分别为 \frac{1}{2},\frac{1}{3},\frac{1}{3}

2. 枚举所有可能的颜色状态，共有 $2^3 = 8$ 种状态：

   • 状态 000：所有节点都是棕色，红色连通块数为 0。
   • 状态 001：节点 3 是红色，红色连通块数为 1。
   • 状态 010：节点 2 是红色，红色连通块数为 1。
   • 状态 011：节点 2 和 3 是红色，红色连通块数为 2。
   • 状态 100：节点 1 是红色，红色连通块数为 1。
   • 状态 101：节点 1 和 3 是红色，红色连通块数为 1。
   • 状态 110：节点 1 和 2 是红色，红色连通块数为 1。
   • 状态 111：所有节点都是红色，红色连通块数为 1。

3. 计算每个状态的概率并加权求和得到期望值 $\frac{5}{6}$ 。 逆元的相关提示：费马小定理有当模数为素数时， $\forall x\text{不同余于}0;x^{p-1}\equiv 1$ ，故 $x^{p-2}$ 为 $x$ 的逆元。

数据范围：