P14975 [HackerEarth] Consider an NXN matrix on which the possible moves from a given block (i,j), is either one upward (i+1, j), or one rightward (i, j+1) or one diagonally up (i+1, j+1).
普及
题目描述

Consider an NXN matrix on which the possible moves from a given block (i,j), is either one upward (i+1, j), or one rightward (i, j+1) or one diagonally up (i+1, j+1).
As shown in figure:

assuming that the numbering of rows and columns starts from 1.

You have to tell number of ways one can reach from block [a][b] to block [c][d].
Since this number may be huge print your answer modulo 1000000007.

Input:

 First line T, the number of test cases

 T lines containing four space separated integers a,b,c,d.

Output:

  T lines with required answer Modulo 1000000007 for each test case.

Constraints:

  1 ≤ T ≤ 100000

  1 ≤ a ,b ≤ c,d ≤ 1004

SAMPLE INPUT
3
1 1 1 2
1 1 2 2
1 2 2 3

SAMPLE OUTPUT
1
3
3

输入格式

见题面

输出格式

见题面

样例输入
144 800 812 801 813 800 812 801 814 800 812 801 815 800 812 801 816 800 812 801 817 800 812 801 818 800 812 801 819 800 812 801 820 800 812 801 821 800 812 801 822 800 812 801 823 800 812 801 824 800 812 802 813 800 812 802 814 800 812 802 815 800 812 802 816 800 812 802 817 800 812 802 818 800 812 802 819 800 812 802 820 800 812 802 821 800 812 802 822 800 812 802 823 800 812 802 824 800 812 803 813 800 812 803 814 800 812 803 815 800 812 803 816 800 812 803 817 800 812 803 818 800 812 803 819 800 812 803 820 800 812 803 821 800 812 803 822 800 812 803 823 800 812 803 824 800 812 804 813 800 812 804 814 800 812 804 815 800 812 804 816 800 812 804 817 800 812 804 818 800 812 804 819 800 812 804 820 800 812 804 821 800 812 804 822 800 812 804 823 800 812 804 824 800 812 805 813 800 812 805 814 800 812 805 815 800 812 805 816 800 812 805 817 800 812 805 818 800 812 805 819 800 812 805 820 800 812 805 821 800 812 805 822 800 812 805 823 800 812 805 824 800 812 806 813 800 812 806 814 800 812 806 815 800 812 806 816 800 812 806 817 800 812 806 818 800 812 806 819 800 812 806 820 800 812 806 821 800 812 806 822 800 812 806 823 800 812 806 824 800 812 807 813 800 812 807 814 800 812 807 815 800 812 807 816 800 812 807 817 800 812 807 818 800 812 807 819 800 812 807 820 800 812 807 821 800 812 807 822 800 812 807 823 800 812 807 824 800 812 808 813 800 812 808 814 800 812 808 815 800 812 808 816 800 812 808 817 800 812 808 818 800 812 808 819 800 812 808 820 800 812 808 821 800 812 808 822 800 812 808 823 800 812 808 824 800 812 809 813 800 812 809 814 800 812 809 815 800 812 809 816 800 812 809 817 800 812 809 818 800 812 809 819 800 812 809 820 800 812 809 821 800 812 809 822 800 812 809 823 800 812 809 824 800 812 810 813 800 812 810 814 800 812 810 815 800 812 810 816 800 812 810 817 800 812 810 818 800 812 810 819 800 812 810 820 800 812 810 821 800 812 810 822 800 812 810 823 800 812 810 824 800 812 811 813 800 812 811 814 800 812 811 815 800 812 811 816 800 812 811 817 800 812 811 818 800 812 811 819 800 812 811 820 800 812 811 821 800 812 811 822 800 812 811 823 800 812 811 824 800 812 812 813 800 812 812 814 800 812 812 815 800 812 812 816 800 812 812 817 800 812 812 818 800 812 812 819 800 812 812 820 800 812 812 821 800 812 812 822 800 812 812 823 800 812 812 824
样例输出
3 5 7 9 11 13 15 17 19 21 23 25 5 13 25 41 61 85 113 145 181 221 265 313 7 25 63 129 231 377 575 833 1159 1561 2047 2625 9 41 129 321 681 1289 2241 3649 5641 8361 11969 16641 11 61 231 681 1683 3653 7183 13073 22363 36365 56695 85305 13 85 377 1289 3653 8989 19825 40081 75517 134245 227305 369305 15 113 575 2241 7183 19825 48639 108545 224143 433905 795455 1392065 17 145 833 3649 13073 40081 108545 265729 598417 1256465 2485825 4673345 19 181 1159 5641 22363 75517 224143 598417 1462563 3317445 7059735 14218905 21 221 1561 8361 36365 134245 433905 1256465 3317445 8097453 18474633 39753273 23 265 2047 11969 56695 227305 795455 2485825 7059735 18474633 45046719 103274625 25 313 2625 16641 85305 369305 1392065 4673345 14218905 39753273 103274625 251595969