Background

Description

给定 $p,n,l,r$，请对0到$p-1$的所有值$a$，输出满足$l\le x\le r$且$\dbinom{x}{n}\equiv a(\mod p)$的个数满足模998244353的值。

Input

一行四个数，分别表示p,n,l,r。

Output

p行，第i行表示a=i-1时的答案。

Samples

7 3 1 7

3
1
0
1
1
0
1

Data Constraint

对于 $10$ 的数据，$n,l,r \le 1000$。

对于 $20$ 的数据，$n,l,r \le 100000$。

对于另外 $20$ 的数据，$r-l \le 10000$。

对于另外 $30$ 的数据，$p\le 1000$，且某些数据点中$p\le 100$。

对于$100$的数据，$p\le 30000,l,r,n\le 10^{30}$，

$p$是质数。

此外为了照顾被卡常的同学，本题存在过渡数据。

为了照顾不知道高精度的小朋友，在各种类型的数据中分布一些$l,r,n\le 10^{18}$的数据。

Hint

$$\dbinom{1}{3}=\dbinom{2}{3}=0 \equiv 0(\mod 7)\\\\ \dbinom{2}{3}=1 \equiv 1(\mod 7)\\\\ \dbinom{4}{3}=4 \equiv 4(\mod 7)\\\\ \dbinom{5}{3}=10 \equiv 3(\mod 7)\\\\ \dbinom{6}{3}=20 \equiv 6(\mod 7)\\\\ \dbinom{7}{3}=35 \equiv 0(\mod 7)\\\\ $$

故模7意义下值为0的有三个，值为$1,3,4,6$的各一个，因此样例输出即为所求答案