1606 - hack大赛

通过次数

7

提交次数

13

Time Limit : 3 秒
Memory Limit : 512 MB

一场Codeforces马上就要结束了,小林已经通过做题得到了C分,但他惊讶地发现房间里的其他选手都解决了最难的题。小林根据经验断定,大多数的选手都会FST(当然除去rating最高的选手FailedSystemTest)。在此之前。小林想要hack他们,使自己的得分更高。

除了小林,房间里有n个选手,他们已经被按照rating从小到大排序了。当小林成功hack了第i个选手时,他会获得i分的收入。假设小林的hack技术十分高超,百发百中,可以hack除了FailedSystemTest和自己以外的所有选手,而且在此期间没有其他选手干扰。

由于小林有谦虚的美德,他不想让自己的得分太高。小林想要知道,小林想要知道存在着多少种不同的选择一些人hack的方案,使得他的得分在L和R之间。显然,答案会很大,请输出答案对998244353取模后的结果。

Input

1行4个整数:n,C,L,R。其含义如题面所示。

Output

一行一个非负整数,表示方案数。

Examples

Input

5 13 14 17

Output

6

Hint

【数据规模】

对于20%的数据满足:n≤50。

对于50%的数据满足:n≤2000。

对于100%的数据满足:1≤n≤100000,1≤C≤1000000,C≤L≤R<C+n。

Source

课课通