题目描述

在一个 R 行 C 列的表格里，我们要选出 3 个不同的单元格。但要满足如下的两个条件：

1. 选中的任意两个单元格都不在同一行。

2. 选中的任意两个单元格都不在同一列。

假设我们选中的单元格分别是：A，B，C，那么我们定义这种选择的 “费用” = f[A][B] + f[B][C] + f[C][A] 。其中 f[A][B] 是指单元格 A 到单元格 B 的距离，即两个单元格所在行编号的差的绝对值 + 两个单元格所在列编号的差的绝对值。例如：单元格A在第3行第2列，单元格B在第5行第1列，那么f[A][B] = |3-5| + |2-1| = 2 + 1 = 3。至于f[B][C], f[C][A]的意义也是同样的道理。现在你的任务是：有多少种不同的选择方案，使得“费用”不小于给定的数minT，而且不大于给定的数 maxT ，即“费用”在 [minT, maxT] 范围内有多少种不同的选择方案。答案模 1000000007 。所谓的两种不同方案是指：只要它们选中的单元格有一个不同，就认为是不同的方案。

输入格式

一行，4 个整数， R、C、minT、maxT ( 3 ≤ R , C ≤ 4000 , 1 ≤ minT ≤ maxT ≤ 20000 )。

对于 30% 的数据, 3 ≤ R ，C ≤ 70 。

输出格式

一个整数，表示不同的选择方案数量模 1000000007 后的结果。

样例

3 3 1 20000

6

3 3 4 7

0

4 6 9 12

264

7 5 13 18

1212

4000 4000  4000  14000

859690013