状态数是\(O(nm^2)\)的DP很好想，就是\(dp_{i,l,r}\)表示第\(i\)次的区间为\([l,r]\)的方案数。但是这个状态数就已经死了，而题目又提示\(n\timesm\leq1e7\)，说明状态只能形如\(dp_{i,j}\)。这时就会想到一个简陋的打补丁方式：设\(f_{i,l},g_{i,r}\)分别表示第\(i\)

题意：给定\(n,m\)，一个区间序列\(\{[L_1,R_1],[L_2,R_2],\cdots,[L_n,R_n]\}\)被称为好的当且仅当：\(\foralli\in[1,n],1\leL_i\leR_i\lem\)。\(\foralli\in[1,n-1],[L_i,R_i]\cup[L_{i+1},R_{i+1}]\ne\emptyset\)。输出好的序列个数对给定质数\(p\)