题目背景

xxx 开发了一种新的象棋：果鸡象棋！最近它在研究果鸡象棋的$10^{4514}$种绝杀方法。

题目描述

有一个$n\times m$的棋盘，每个位置恰好有一个棋子，这个棋子只可能是苹果、象或者鸡。最初棋盘上没有鸡，只有象和苹果，xxx 想将若干苹果替换成鸡，使得不存在两只不同的鸡互相攻击。两个不同的鸡互相攻击的定义为：它们在同一行或同一列，且它们的最短路径上不存在象。

显然，鸡数量的一个上界是$nm$。设$F(x)$表示将$x$个苹果替换成鸡且所有鸡互不攻击的方案数，$\forall x\in[0,nm]$，求$F(x)$。

xxx 发现这个问题太简单了，所以它将问题改成了：对于$2^{n\times m}$种棋盘的原状态，求答案之和。也即，设$sF(x)$表示对于$2^{n\times m}$种棋盘的初始状态，将$x$个苹果替换成鸡且所有鸡互不攻击的方案数之和。$\forall x\in[l,r]$，求$sF(x) \mod 998244353$。

输入格式

输入四个正整数$n,m,l,r$。

输出格式

输出$r-l+1$行，第$i$行输出$sF(i+l-1)\mod 998244353$。

样例1输入

2 2 0 4

样例1输出

16
32
8
0
0

样例2输入

3 2 0 6

样例2输出

64
192
112
8
0
0
0

数据范围

对于100\%的数据，$n\leq 6,nm\leq 30000$，保证$0\leq l\leq r\leq nm$。

• Sub1(3pts): $n\leq 4,l=nm$
• Sub2(7pts): $n\leq 3,m\leq 5$
• Sub3(5pts): $n\leq 4,l=r\leq 2$
• Sub4(10pts): $n\leq 4,l=r\leq 3$
• Sub5(15pts): $n\leq 1,l=r$
• Sub6(10pts): $n\leq 4$
• Sub7(20pts): $n\leq 5$
• Sub8(30pts): $n\leq 6$

$4s,1G$