P9862 [HackerEarth] going to indiahacks
普及
题目描述

As of now you have registered for IndiaHacks 2016 which is about to begin and you want to go to the venue to participate and the map is in the form of matrix. 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 you can reach from block [a][b] i.e. your home to block [c][d] i.e Indiahacks venue.
Since this number may be huge print your answer modulo 1000000007.

Still if you have not registered for the contest do it now at IndiaHacks 2016 else Tom and Jerry will fight with you at the venue.

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

Register for IndiaHacksSAMPLE INPUT
3
1 1 1 2
1 1 2 2
1 2 2 3

SAMPLE OUTPUT
1
3
3

Register for IndiaHacks

输入格式

见题面

输出格式

见题面

样例输入
144 120 12 121 13 120 12 121 14 120 12 121 15 120 12 121 16 120 12 121 17 120 12 121 18 120 12 121 19 120 12 121 20 120 12 121 21 120 12 121 22 120 12 121 23 120 12 121 24 120 12 122 13 120 12 122 14 120 12 122 15 120 12 122 16 120 12 122 17 120 12 122 18 120 12 122 19 120 12 122 20 120 12 122 21 120 12 122 22 120 12 122 23 120 12 122 24 120 12 123 13 120 12 123 14 120 12 123 15 120 12 123 16 120 12 123 17 120 12 123 18 120 12 123 19 120 12 123 20 120 12 123 21 120 12 123 22 120 12 123 23 120 12 123 24 120 12 124 13 120 12 124 14 120 12 124 15 120 12 124 16 120 12 124 17 120 12 124 18 120 12 124 19 120 12 124 20 120 12 124 21 120 12 124 22 120 12 124 23 120 12 124 24 120 12 125 13 120 12 125 14 120 12 125 15 120 12 125 16 120 12 125 17 120 12 125 18 120 12 125 19 120 12 125 20 120 12 125 21 120 12 125 22 120 12 125 23 120 12 125 24 120 12 126 13 120 12 126 14 120 12 126 15 120 12 126 16 120 12 126 17 120 12 126 18 120 12 126 19 120 12 126 20 120 12 126 21 120 12 126 22 120 12 126 23 120 12 126 24 120 12 127 13 120 12 127 14 120 12 127 15 120 12 127 16 120 12 127 17 120 12 127 18 120 12 127 19 120 12 127 20 120 12 127 21 120 12 127 22 120 12 127 23 120 12 127 24 120 12 128 13 120 12 128 14 120 12 128 15 120 12 128 16 120 12 128 17 120 12 128 18 120 12 128 19 120 12 128 20 120 12 128 21 120 12 128 22 120 12 128 23 120 12 128 24 120 12 129 13 120 12 129 14 120 12 129 15 120 12 129 16 120 12 129 17 120 12 129 18 120 12 129 19 120 12 129 20 120 12 129 21 120 12 129 22 120 12 129 23 120 12 129 24 120 12 130 13 120 12 130 14 120 12 130 15 120 12 130 16 120 12 130 17 120 12 130 18 120 12 130 19 120 12 130 20 120 12 130 21 120 12 130 22 120 12 130 23 120 12 130 24 120 12 131 13 120 12 131 14 120 12 131 15 120 12 131 16 120 12 131 17 120 12 131 18 120 12 131 19 120 12 131 20 120 12 131 21 120 12 131 22 120 12 131 23 120 12 131 24 120 12 132 13 120 12 132 14 120 12 132 15 120 12 132 16 120 12 132 17 120 12 132 18 120 12 132 19 120 12 132 20 120 12 132 21 120 12 132 22 120 12 132 23 120 12 132 24
样例输出
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