301045 / 雷的打字机
题号：NC25163
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

雷靠当妈妈的间谍得到了一台精致的打字机。菲尔对这台打字机充满了好奇。
一天，他开始捣鼓这台打字机。这台打字机上有 n 个按键，每个按键对应一个字符，且这 n 个字符两两不同。每次按下一个按键时，打字机就会打印出一个对应的字符。打印出的字符顺次连接可以得到一个打印出的字符串。
菲尔不想用这台打字机写什么文章。每次他有 p_i 的概率按下第 i 个按键，当打印出的字符串存在任意一个长度为偶数的回文子串时，他就会停止按按键。他想知道，打印出的字符串的期望长度是多少。

如果你回答不出来的话，菲尔就只好去问诺曼咯。

p 数组是随机生成的，随机种子为 seed 。具体的生成方式为：（C / C++ 代码）
int p[10000011], n;
namespace Generator {
    unsigned int seed;
    int Rand() {
        seed = (seed << 2) ^ (seed >> 5) ^ (seed << 7) ^ (seed >> 11);
        return seed % 998244353;
    }
    void Generate() {
        int sum = 0;
        for (int i = 1; i < n; ++i) {
            p[i] = Rand();
            sum = (sum + p[i]) % 998244353;
        }
        p[n] = (998244354 - sum) % 998244353;
    }
}
C / C++ 选手可以选择复制该代码段到你的程序中。在读入 n 以及 Generator::seed 后，调用 Generator::Generate() 即可生成 p 数组。
该段代码的意义是，读入 seed 之后，p_1 至 这 n-1 个数依次由 Rand() 生成。为使总概率等于 1 ，p_n 等于 。注意此处 seed 是 unsigned int 类型，生成所得的 p 数组是在模 998244353 意义下的。


输入描述:

输入仅一行，包含两个整数 n, seed 。意义如题面所述。

输出描述:

输出仅一行，包含一个整数，表示答案。你需要输出答案在模 998244353 意义下的值。
即设答案化为最简分式后的形式为  ，其中 a 和 b 互质。输出整数 x 使得  且 。可以证明这样的整数 x 是唯一的。
示例1

输入

复制 
3 666

输出

复制 
334710210

说明

p 数组为 [83836, 10922467, 987238051] 。
此处再额外给一组良心样例：若 p 数组为 [{1 \over 2}, {1 \over 2}]，ans = 3。

备注: