Alice is a programmer who holds three accounts, each having a rating value denoted by integers a, b, and c. During the next N contests, the rating of any one of the accounts will increase or decrease by 1. This means rating value [a, b, c] will become [a+1, b, c] or [a-1, b, c] or [a, b+1, c] or [a, b-1, c] or [a, b, c+1] or [a, b, c-1]. Two ways are considered different if, after any contest, the rating of at least one of the accounts is different. Ratings can be negative.

She participates in N such contests. Initially, the rating of all accounts was 0. Find the number of ways such that by the end of the N^th contest rating, the three accounts will exactly become A, B, and C, respectively. Since the answer can be large, print it modulo 1000000007.

Function description

Complete the solve() function. This function takes the following four parameters and returns a long integer as the required answer:

• N: Represents the value of N
• A: Represents the value of A
• B: Represents the value of B
• C: Represents the value of C

Input format for custom testing

Note: Use this input format if you are testing against custom input or writing code in a language where we don’t provide boilerplate code.

• The first line contains a single integer T, which denotes the number of test cases. T also specifies the number of times you have to run the solve function on a different set of inputs.
• For each test case:
  • The first line contains 4 space-separated integers N, A, B, C, where N denotes the number of contests and A, B, C denotes the target ratings of the accounts.

Output format

For each test case, print the answer on a new line. As the answer can be too large, print it modulo 1000000007.

Constraints