DCEPC702 - NOS

no tags 

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”.

Input

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

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

Constraints

1<=T<=1000
1<=N<=10^9
1<=min_a<= max_a<=10^9

1<=min_b<= max_b<=10^9

1<=min_c<= max_c<=10^9

Example

Input:

1

3

1 1

1 1

1 1

Output: 1

hide comments
nadstratosfer: 2019-07-13 17:52:09

Hit the wall in what seemed to be the easy part of the computation but rather than postponing until I can look at it again with a fresh mind, produced a massive overkill about 50 lines too long, with an extra log factor to boot, that took an hour to debug, and dragged this convoluted mess past the finish line. Even a broken clock gives the right time twice a day, lol. Cool problem though.

aspro: 2016-05-21 20:39:34

great question....just take care while using combination and modulo together.

Smriti Vashisth: 2014-06-08 16:32:30

can anyone give some more test cases, I'm getting WA after running 5th case

Rishav Goyal: 2014-03-28 13:30:38

@D: Great Idea.. !!!

Deepak: 2014-02-24 21:10:02

As easy as they come...

(Tjandra Satria Gunawan)(曾毅昆): 2012-09-28 11:37:26

My Math Formula give me perfect time 0.00s ;-)

:D: 2012-07-02 07:00:16

Nonsense! Testing with values in range (1;1000) will find pretty much all issues you can have with your program on problem like this. What could be left, is checking for proper usage of data types (long long/int). In fact, I'm pretty sure your program fails on some cases where a,b,c<=10.

Last edit: 2012-07-02 14:09:34
Gaurav Mittal: 2012-06-28 06:15:54

i understand but please answer my ques., because brute force is not the solution for my problem

:D: 2012-06-27 10:06:10

You can easily write a brute force checker and analyze some smaller cases on your own. Just check all ordered "abc" strings separately to see if they meet constraints. It will be only O(N^2) and you will be able to check pretty big test cases with it.

How do you expect to debug programs on your own if you don't use brute force to check solutions?

Gaurav Mittal: 2012-06-27 09:28:47

Is the output for
1000000000
1 1000000000
1 1000000000
1 1000000000

36 ??


Added by:dce coders
Date:2012-04-30
Time limit:0.185s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem