Problem Statement
You are playing a computer game. Your army consists of B+H warriors: B bears and H humans. A bear has 2 hit points, and a human has 1 hit point.
There is an enemy archer equipped with T arrows. He shoots them one at a time, each time hitting a random warrior (chosen uniformly at random among your warriors that are still alive). A hit warrior loses 1 hit point, and dies immediately if his hit points become 0.
The strength of your army is defined as the product of three values: bears*humans*warriors. For example, if there are 3 bears and 10 humans still alive, the army strength is 3*10*13=390. It doesn't matter whether some bears are wounded (i.e. they have only 1 hit point).
Find the expected value of the army strength when the enemy archer runs out of arrows. Represent the answer as a reduced fraction P/Q. (That is, P and Q must be relatively prime.) For the constraints specified below Q will never be divisible by 10^9 + 7. Compute and return the value P*Q^{-1} modulo (10^9 + 7).
Definition
- Class:
- DoubleLive
- Method:
- findEV
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int findEV(int B, int H, int T)
- (be sure your method is public)
Constraints
- B will be between 1 and 2000, inclusive.
- H will be between 1 and 2000, inclusive.
- T will be between 0 and 2*B+H, inclusive.
Examples
4
3
1
Returns: 571428644
The army consists of 4 bears and 3 humans. The enemy archer shoots 1 arrow. With probability 4/7 the arrow will hit one of the bears. A bear loses 1 hit point but doesn't die. The army strength is 4*3*7=84. With probability 3/7 the arrow will hit one of the humans. A human loses 1 hit point and dies. The army will have 4 bears and 2 humans, with total strength 4*2*6=48. The answer is 4/7 * 84 + 3/7 * 48 = 480/7.
3
10
0
Returns: 390
The enemy archer has no arrows, so your whole army survives. The strength is 3 * 10 * 13 = 390.
1
2
2
Returns: 111111113
The army consists of 1 bear and 2 humans. There will be 2 arrows. With probability 1/3 the first arrow hits the only bear. He loses 1 hit point. Then with probability 1/3 the second arrows hits the same bear and thus he dies. The army strength is 0*2*2=0. With probability 1/3 the first arrow hits the only bear, and then with probability 2/3 the second arrow hits and kills one of two humans. The army strength is 1*1*2=2. With probability 2/3 the first arrow hits and kills one of two humans. Then, 1 bear and 1 human remain. The second arrow will hit and kill the human with probability 1/2, and otherwise it will wound the bear. The army strength will be 1*0*1=0 and 1*1*2=2, respectively. The answer is 1/9 * 0 + 2/9 * 2 + 1/3 * 0 + 1/3 * 2 = 0 + 4/9 + 0 + 2/3 = 10/9.
1
1
1
Returns: 1
1
1
2
Returns: 0
3
10
16
Returns: 0
Everybody will die :(
5
2
5
Returns: 519487272
1807
1234
4040
Returns: 373880953
20
10
7
Returns: 226540738
2000
2000
5998
Returns: 838671441
1987
1701
570
Returns: 615965054
2
3
2
Returns: 600000018
3
2
2
Returns: 200000017
5
1
4
Returns: 422222235
1
5
4
Returns: 116666671
1
1
0
Returns: 2
1
1
1
Returns: 1
1
1
2
Returns: 0
1
1
3
Returns: 0
5
1
0
Returns: 30
1
5
0
Returns: 30
5
1
11
Returns: 0
1
5
7
Returns: 0
1
5
5
Returns: 766666673
5
1
9
Returns: 350942801
2000
2000
0
Returns: 999999895
2000
2000
1
Returns: 994000895
2000
2000
3786
Returns: 60010987
2000
2000
5997
Returns: 625521373
2000
2000
5999
Returns: 0
2000
2000
6000
Returns: 0
2000
2000
5998
Returns: 838671441
2000
1970
5860
Returns: 216626432
1981
2000
123
Returns: 814683669
1981
2000
5887
Returns: 768995487
1457
1612
3970
Returns: 239833859
1910
1844
4567
Returns: 686147294