You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述 2.5s 512MB

小明种了$n$颗水稻，它们排成一排。

由于这$n$颗水稻的品种不一样，所以它们需要灌溉的水量也不一样，具体地：第$i$颗水稻需要被灌溉$[a_i,b_i]$单位之间的水，多了会淹死，少了会旱死。

小明每次可以给一个区间$[L_i,R_i]$浇水，这会使得这个区间每颗水稻的水量$+1$。

小明决定一共浇水$m$次。

问：小明有多少种方法浇水，可以使得每一颗水稻都能得到需要的水。

输入格式

第一行输入$n,m$。

第二行输入$n$个数字表示$a_1,...,a_n$。

第三行输入$n$个数字表示$b_1,...,b_n$。

输出格式

输出一个数字代表答案$\mod 998244353$。

2 2
1 1
2 2

7

样例解释 #1

每次浇水有三种选择：$[1,1],[2,2],[1,2]$。所以一共有$9$种方案。

只要两次不同时是$[1,1]$或者$[2,2]$，就是合法的方案。

所以一共有$7$种合法方案。

3 2
1 1 1
2 2 2

17

样例解释 #2

每次浇水一共有$6$种选择。

假设第一次是$[1,3]$，那么后续$6$种情况都合法。

假设第一次是$[1,2]$，那么后续包含$3$的$3$种情况都合法。

假设第一次是$[2,3]$，那么后续包含$1$的$3$种情况都合法。

假设第一次是$[1,1]$，那么后续$[1,3],[2,3]$都合法。

假设第一次是$[3,3]$，那么后续$[1,3],[1,2]$都合法。

假设第一次是$[2,2]$，那么后续只有$[1,3]$合法。

共$6+3+3+2+2+1=17$种方案。

10 15
1 2 1 1 3 2 1 1 1 5
2 5 3 4 5 8 6 4 2 6

216644318

100 300
11 16 17 15 19 17 15 15 14 16 12 13 11 14 19 9 13 18 17 16 17 11 13 13 17 17 19 18 13 12 16 16 19 23 13 15 16 13 19 13 11 12 16 23 14 8 13 19 13 13 29 12 15 16 10 9 12 13 11 14 15 19 11 22 23 20 8 20 10 13 17 18 16 21 15 12 22 13 9 13 15 11 19 12 16 22 14 13 14 12 14 15 13 18 19 15 10 23 11 8 
281 283 288 283 287 287 285 281 287 283 291 291 290 288 286 282 281 291 286 289 279 281 288 286 290 287 283 284 285 283 287 278 283 276 281 282 280 290 290 279 287 293 286 284 277 286 287 288 284 286 287 291 291 285 291 287 286 282 287 286 286 284 284 282 284 280 282 282 279 282 284 284 292 284 285 284 278 284 288 281 284 282 289 289 292 291 284 287 280 290 280 280 286 284 286 279 285 289 289 286 

577583272

数据范围

对于5%的数据：$l_i=0,r_i=m$。

对于另15%的数据：$n,m\leq 5$。

对于另10%的数据：$n\leq 100,m=2$。

对于另15%的数据：$n\leq 50,m=3$。

对于另25%的数据：$n,m\leq 50$。

对于另15%的数据：$n,m\leq 100$。

对于100%的数据：$n\leq 100,m\leq 300,0\leq l_i,r_i\leq m$。