#include<bits/stdc++.h>
#define rg register 
#define step inline void
typedef unsigned long long ull;
typedef long long ll;
const int maxi=+9;
using namespace std;
inline int read(){
	rg int x=0;rg char c=getchar();
	for(;!isdigit(c);c=getchar());
	for(;isdigit(c);x=(x<<3)+(x<<1)+(c^48),c=getchar());
	return x;
	
}
int main(){
	freopen("query.in","r",stdin);
	freopen("query.out","w",stdout);
	return 0;
}
/*
虽然我知道考场写游记是不正确的， 
但是没办法， 
我太激动了， 
因为刚刚T2样例全过，
如果不挂200分基本稳了。
T1略，总之就是看错题了然后重新想然后想对了。
T2讲真的我真没想到我能做出来，
总之先想出来了特殊性质A，然后想出来了M=1，
然后就忽然意识到，这个问题可以拆分成上述两种情况
所以我只需要按c的大小sort一遍然后遍历限制计算就可以
d甚至没用上。 
有几个结论：
当一段完全没有限制的前缀或后缀随便选a,b，
因为对于这些段来说你只要逆着a来就可以了。 
然后是限制-非限制-限制段，
注意到只有当整段非限制都满足a_i=b_(i-1)时才会产生不合法排列，
所以只需考虑算出来这段不合法排列的数量，用它减去总数量，
然后拿算出来的差给答案乘上就行。
anyway， 
感谢教练！感谢队友！感谢父母！感谢班主任和年级主任！感谢出题人！ 
感谢HSAS！感谢清北网校！感谢云豆学院！ 
感谢南国神机！感谢524、525和523！
感谢鼠标！感谢键盘！感谢显示屏！
感谢CSP-s！ 
*/ 
