#P11062. [2016杭电多校]Zhu’s Math Problem

    ID: 10204 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 7 上传者: 标签>CF2200提高数位 DP上界限制状态滚动数组预计算转移

[2016杭电多校]Zhu’s Math Problem

Zhu’s Math Problem

Problem Description

Zhu is a powerful ACMer/OverWatcher, now a salt-fish comes to ask Zhu a difficult problem. Zhu thinks that problem is so easy, so he wants to know whether you can solve it? The problem content are as follows. You are given four integers A , B , C , D , there are many different (a,b,c,d) satisfy a+c>b+da+c>b+d && a+d≥b+ca+d\ge b+c && 0≤a≤A0\le a\le A && 0≤b≤B0\le b\le B && 0≤c≤C0\le c\le C && 0≤d≤D0\le d\le D ?

Input

First Line is an positive integer T(T≤1000)T(T\le 1000) , represents there are T test cases. Four each test: The first line contain four integers A , B , C , D. You can assume that 0≤A,B,C,D≤10180\le A,B,C,D\le 10^{18}

Output

For each test case, output an positive integer represents answer, because the answer may be large , so you are only need to output answer mod 109+710^9+7

Sample Input

1
2 1 1 1

Sample Output

10

Author

UESTC

Source

2016 Multi-University Training Contest 6