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

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

hide comments
2012-06-27 09:28:47 Gaurav Mittal
Is the output for
1000000000
1 1000000000
1 1000000000
1 1000000000

36 ??
2012-06-22 06:31:46 Suraj D
@Aman Kumar .Some more test cases please.
2012-06-17 15:28:18 Pandian
Thanks Aman :) Then, where I m going wrong ?? Any tricky cases ??
2012-06-04 07:51:41 Aman Kumar
awesome prob. :)
yes Pandian, the output is,
999849973

Last edit: 2012-06-04 08:31:33
2012-05-25 17:43:15 Pandian
Is the output for
100000
1 100000
1 100000
1 100000

999849973 ??
2012-05-25 13:57:36 Pandian
Can you please give some more test cases ??

Last edit: 2012-05-25 17:42:36
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.