题目描述

一座储能站需要根据未来 $n$ 天的电价安排充放电。假设某一天的电价为 $x$，当天可以执行以下三种操作之一：

1. 支付 $x$ 的费用，为储能站充入一个单位的电能，且一天至多充入一个单位；
2. 以 $x$ 的价格卖出一个单位的电能，且一天至多卖出一个单位，同时当前必须至少储存了一个单位的电能；
3. 不进行任何操作。

储能站初始没有储存电能，并且可用于购电的资金没有限制。它会采用能够使最终净收益最大的操作方案。

现在只知道每天的电价均为 $1$ 或 $2$。请统计有多少种长度为 $n$ 的电价序列，会使储能站能够获得的最大净收益恰好为 $k$。

输入格式

输入共两行，第一行为一个正整数 $tp$，表示询问类型。

若 $tp=1$，则第二行有两个整数 $n,k$，表示天数和要求的最大净收益。

若 $tp=2$，则第二行有一个正整数 $n$，表示天数。

输出格式

若 $tp=1$，则输出一行一个整数 $ans$，表示最大净收益恰好为 $k$ 的电价序列数量。答案对 $998244353$ 取模。

若 $tp=2$，则输出一行一个整数 $ans$。设 $way_k$ 表示最大净收益恰好为 $k$ 的电价序列数量，则

$$ans=\sum_{i=0}^{\lfloor \frac {n} {2} \rfloor} 233^i*way_i\ mod\ 998244353$$

样例

样例输入 1

1
4 2

样例输出 1

2

样例解释

共有两种符合要求的电价序列，分别为 $[1,1,2,2]$ 和 $[1,2,1,2]$。

数据范围与提示

$subtask 1(10pts)$：$n \leq 20$。

$subtask 2(10pts)$：$n \leq 300$。

$subtask 3(10pts)$：$n \leq 5000,tp=1$。

$subtask 4(15pts)$：$n \leq 5000$。

$subtask 5(10pts)$：$n \leq 10^5,tp=1$。

$subtask 6(15pts)$：$n \leq 10^5$。

$subtask 7(10pts)$：$n \leq 10^6,tp=1$。

$subtask 8(20pts)$：$n \leq 10^6$。

对于所有数据，满足 $1 \leq n \leq 10^6,0 \leq k \leq \lfloor \frac {n} {2} \rfloor$