B - Good Predictions

Having arrived at the ACM-ICPC contest site in a fun-filled mood, The Team continues their important pre-contest preparations. Specifically, every world-class team knows the importance of making predictions about their upcoming submissions.

The Team knows that they'll get plenty of AC (Accepted) submissions, and they find those quite boring by now. As such, they'll focus on their incorrect ones. From their vast experience, The Team knows that they'll only get exactly N (1 ≤ N ≤ 300) submissions wrong throughout the upcoming contest - in fact, they predict that, of those, exactly W (0 ≤ W ≤ 100) will get WA (Wrong Answer), T (0 ≤ T ≤ 100) will get TLE (Time Limit Exceeded), and the remaining R (0 ≤ R ≤ 100) will get RE (Runtime Error). Note that W + T + R = N.

Assuming that their predictions will certainly be correct, the members of The Team are wondering in how many ways that might occur. In other words, how many different ordered combinations of N incorrect results (each being WA, TLE, or RE) exist which satisfy their predictions? Since The Team doesn't make many mistakes, surely you can calculate this value, right? However, since it can get quite large for you, compute it modulo (10⁹ + 7).

Input

4 integers, N, W, T, and R

Output

1 integer, the number of valid ordered combinations of submission results, modulo (10⁹ + 7).

Sample Input

3 2 1 0

Sample Output

3

Explanation of Sample

Out of 3 submissions, two are WA, while the third is TLE. The following 3 ordered combinations are then possible:
WA, WA, TLE
WA, TLE, WA
or
TLE, WA, WA
The answer is then 3 modulo (10⁹ + 7) = 3.

All Submissions
Best Solutions

Point Value: 10
Time Limit: 4.00s
Memory Limit: 64M
Added: Jun 01, 2012
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, TEXT, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Some solutions using the mathematical approach get 253344377.

I've got no write privileges to the test case folder, so I can't correct it myself.

The case should be:
[code]286 99 94 93[/code] as opposed to: [code]292 99 94 93[/code]

However, mathematical solutions, in exploiting bignums, should probably be disallowed.

286 99 94 93

292 99 94 93

Haters gonna hate.

Haha, oops... I didn't really expect people to even use the value of N, since it's pointless, so I didn't check it super carefully =P

Thanks for pointing this out. The data's been fixed, and all solutions rejudged.

I won't disallow any solutions - people can use math if they want, I personally find that more difficult anyway.

btw: there is a script that runs every day that makes all the test data writable by the "peg" group