该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

变速带

题目背景

tiger非常喜欢玩游戏。 今天他进行了一次游戏启动，邀请你来看看他的$\tiny\text{并不}$优秀的操作。

题目描述

这一款游戏由 $n+2$ 块地砖构成，编号为 $0\sim n+1$。 第 $1\sim n$ 块地砖被以下 $4$ 种变速带紧挨着覆盖：

1. 加速带Ⅰ：占地 $1$ 格，可以让汽车的速度 $+1$。
2. 加速带Ⅱ：占地 $2$ 格，可以让汽车的速度 $\times 2$。
3. 减速带Ⅰ：占地 $1$ 格，可以让汽车的速度 $-1$。
4. 减速带Ⅱ：占地 $2$ 格，可以让汽车的速度 $\div 2$ (向下取整)。

tiger的汽车初始在编号为 $0$ 的格子上，初始速度为 $1$，他需要去到编号为 $n+1$ 的格子上。 然而，这个道路上全部遍布着 $3$ 种障碍：

1. 地雷：如果tiger的汽车某一刻速度 $\leq 0$，他的汽车将立马爆炸，游戏失败。
2. 监控：如果tiger的汽车某一刻速度 $> k$，他的汽车将立马被拦截，游戏失败。
3. 交警：如果tiger的汽车某一刻倒行（由第 $i$ 格前往第 $i-1$ 格)，他的汽车将立马被锁住，游戏失败。

现在地图上的变速带将由你布置，在布置前你需要知道 $2$ 个问题：

1. 有多少种布置方案可以让tiger成功到达编号为 $n+1$ 的格子，且到达时的速度为 $p$？
2. 有多少种布置方案可以让tiger成功到达编号为 $n+1$ 的格子，且过程中的最大速度为 $q$？

输入格式

一行四个整数 $n,k,p,q$。

输出格式

一行两个整数表示两个问题的答案，对 $998,244,353$ 取模。

样例 #1

样例输入 #1

3 5 4 3

样例输出 #1

2 2

样例 #2

样例输入 #2

4 10 3 6

样例输出 #2

4 1

样例 #3

样例输入 #3

10 9 8 7

样例输出 #3

192 316

样例 #4

样例输入 #4

114 514 191 81

样例输出 #4

503533038 925928033

提示

题面描述中的变速带分别用A-D表示： 样例一： 对于第一问：[A][A][A]和[A][BB]。 对于第二问：[A][A][C]和[BB][A]。 样例二： 对于第一问：[A][A][A][C]，[A][BB][C]，[A][A][C][A]和[A][C][A][A]。 对于第二问：[A][A][BB]。

数据范围

对于 $100\%$ 的数据，$1\leq n\leq 10^3$，$0\leq p,q\leq k\leq2^{13}$，$k\geq 1$。 $\begin{array}{|c|c|c|c|c|}\hline 测试点 & n & k & 特殊限制 & 每点分值\\ \hline 1 & =1 & =2 & / & 1\\ \hline 2 & =2 & \leq4 & / & 1\\ \hline 3\sim 5 & \leq8 & \leq25 & / & 6\\ \hline 6\sim 10 & \leq10^3 & \leq50 & / & 2\\ \hline 11\sim 15 & \leq50 & \leq10^3 & / & 2\\ \hline 16\sim 20 & \leq10^3 & \leq2^{13} & p=0 & 2\\ \hline 21\sim 25 & \leq10^3 & \leq2^{13} & q=0 & 2\\ \hline 26\sim 35 & \leq10^3 & \leq2^{13} & / & 4\\ \hline \end{array} $