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”.
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:
20190713 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:
20160521 20:39:34
great question....just take care while using combination and modulo together. 

Smriti Vashisth:
20140608 16:32:30
can anyone give some more test cases, I'm getting WA after running 5th case 

Rishav Goyal:
20140328 13:30:38
@D: Great Idea.. !!! 

Deepak:
20140224 21:10:02
As easy as they come... 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20120928 11:37:26
My Math Formula give me perfect time 0.00s ;) 

:D:
20120702 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: 20120702 14:09:34 

Gaurav Mittal:
20120628 06:15:54
i understand but please answer my ques., because brute force is not the solution for my problem 

:D:
20120627 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.


Gaurav Mittal:
20120627 09:28:47
Is the output for

Added by:  dce coders 
Date:  20120430 
Time limit:  0.185s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  ASM32GCC MAWK BC CCLANG C C++ 4.3.2 CPP CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JSMONKEY KTLN NIM NODEJS OBJC OBJCCLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  Own Problem 