Design The Construction Site

Time Limit: 3000MS

Memory Limit: 65535KB

Description

南京施工大学为了迎接校庆,要对矩形工地连夜加急施工。在这个工地上规划设计了三种模块,分别是1x1,2x1和1x2的正方形或矩形模块,设计师要用这三种模块填满整个矩形工地。由于分配正方形1x1模块在美观性上有特殊的要求,所以校领导对矩形工地中的1x1模块的数目进行了限制。因为有很多个矩形工地,设计师忙不过来了。他向你寻求帮助,对于给定的一个矩形工地和1x1模块的限制数目,设计师能够给出多少种方案呢?

Input

多Case(约400000个),以EOF结尾

每行即为一个Case,四个整数:n m c d

n x m即为矩阵工地的规模,0<n<=100,0<m<=10;

c d为该矩阵工地的1x1模块的限制,表示该工地上此1x1模块数目不小于c并且不大于d,0<=c<=d<=20

Output

每行输出对应的方案数,答案模除1000000007后输出。

Sample Input

1 1 0 0
1 1 1 2
1 2 1 2
1 2 0 2
2 2 0 0

Sample Output

0
1
1
2
2

Hint

None

Source

李翔

提交代码