SP11473 DCEPC702 - NOS

Find the number of strings of length “N” made up of only 3 characters – a, b, c such that “a” occurs at least “min\_a” times and at most “max\_a” times, “b” occurs at least “min\_b” times and at most “max\_b” times and “c” occurs at least “min\_c” times and at most “max\_c” times. Note that all permutations of same string count as 1, so “abc” is same as “bac”.

First line gives T, the number of test cases. Each test case has an integer “N” on first line. Next line contains 2 integers, min\_a and max\_a. Next line contains 2 integers, min\_b and max\_b. Next line contains 2 integers, min\_c and max\_c.

Output T lines, each containing the required answer modulo 10^9+7.