T2
杨氏矩阵+钩子定理的裸题。
不懂的看我上篇博客：
https://www.cnblogs.com/Lrefrain/p/12245356.html
然后发现这个题问的就是有多少种方案来把需要打的关全都打了。
此处的方案不同指通关顺序不同。
我们发现需要通关的部分两个平行四边形的并，不是杨氏矩阵的形状。
考虑直接给扭成矩形方便计数。
于是改变坐标，使得\(A=A-B+1,C=C-D+1\)，这样就转过来了。
现在是两个矩形的并
直接用钩子定理即可。
我们预处理阶乘，然后再预处理阶乘的前缀积即可。
这样在查询的时候需要求逆元，复杂度是\(O(qlog1e9)\)的。
具体来说可以把这个矩形的并拆开来算。
如果这个并是两个中某一个矩形，那么就可以直接算这一个矩形了。
细节很多我懒得说。
总之，用阶乘和阶乘的前缀积可以算，一些规律自己手玩就行了。
原文：https://www.cnblogs.com/Lrefrain/p/12245379.html