梦境（dream.cpp/.in/.out）0.5s 512MB

题目描述

求最长上升子序列无论在课程、考试还是面试中是永恒的经典问题。因此为了考察同学们上课时有没有认真听讲并努力送分，助教小明找到了⼀个数列 $A_i$ ，准备在期末考试里出一道最长上升子序列的题目考考大家。

我们的助教小明是一个认真负责的好学⽣，因此他在制作标准数据时做了额外的⼯作。他不仅计算了 $\{A_i\}$ 的最长上升子序列的长度 $\{F_i\}$ 表示以 $i$ 为结尾的最长上升子序列的长度。

小明有一个可爱温和的女朋友小红，在小明努力出题的每一个夜晚，小红都会贴在小明⾝边，和他一起讨论题⽬，出谋划策，打情骂俏。小红也是一个乐观善良的好女孩，因此，每晚结束时，她会偷偷地将数字从数列 $\{A_i\}$ 中抽掉，减少数列的长度，进一步弱化数据，希望能有更多大信科的同学在期末考试中拿到更好的分数。

在第 $N$ 天时，正准备抽走一个数字的小红突然发现 $\{A_i\}$ 这个数列已经被她抽空了！小红吓了一跳，小明也吓了一跳，没有了测试数据可怎么出题啊！

这一吓，小明彻底惊醒过来。小红并不存在，和女朋友的依偎只是大梦一场。窗外是北方凌冽的寒风，身后是有爱的中文系情侣，在图书馆苍白的灯光之下，屏幕里闪烁的光标之前，孤独的小明，发现了自己是一个单身狗的事实！想到这里，他鼻子一酸，嚎啕⼤哭。

为了安慰小明，你决定帮助我们善良的助教复现他梦中的美好时光。但尴尬的是，小明只记得数列 $F_i$ 的内容的生成方法，但 $\{A_i\}$ 已经忘得一干⼆净了！作为助教的好兄弟，你表示助教有难，两肋插刀！

说干就干，你操起键盘，开始计算，因为你不确定原来的 $\{A_i\}$ 到底是哪一种，所以你决定计算所有可能的 $\{A_i\}$ 每一个位置最大可能是多大，得到数列 $\{B_i\}$ ，因为数太多了，所以你决定将结果 Hash 后输出

输入格式

第一行三个数 $N,Lim$ 以及生成数据使用的种子 $seed$

$N$ 表示数列的长度，生成的 $F_i$ 满足 $0<F_i\leq Lim$

生成 $F_i$ 只需要调用以下函数 $gen$ 即可 (见下发文件中的 dream_gen.cpp)

static inline
int __my_rand (int *seed) {
    *seed = *seed * 1103515245 + 12345;
    return ((unsigned)*seed) / 34;
}
int gen (int N, int Lim, int seed, int* F) {
    int cur = 0;
    for (int i = 0; i < N; i ++) {
        int rd = __my_rand(&seed);
        if (rd % std::min(10, cur + 1) == 0 && cur < Lim) F[i] = ++cur;
        else F[i] = (__my_rand(&seed) % cur) + 1;
    }
    return 0;
}

输出格式

输出包含一行，为答案经过 Hash 后的结果

输出 $\sum_{i=1}^N 131^i\cdot B_i\mod 998244353$

样例输入1

5 3 13213

样例输出1

837251768

样例解释1

生成的数列 $F$ 为 1 2 3 3 1

对应的数列 $B$ 为 2 3 5 4 1

样例输入2

10 5 23131232

样例输出2

243313812

样例解释2

生成的数列 $F$ 为 1 1 2 1 3 4 4 2 5 3

对应的数列 $B$ 为 10 4 6 1 7 10 8 4 10 6

数据范围

对于所有数据，保证 $n\le 10^7$

测试点编号	特殊性质
1~2	$n\le 10$
3~6	$Lim = 2$
7~10	$Lim = 10$
11~20	无特殊限制