ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2016

About     Problems     Submit solution     Judge status     Standings
Contest is over

K. Nostalgic Evening

Time limit: 2.0 second
Memory limit: 256 MB
Sasha and Slava inhabit sunny California, work at large successful companies and are totally content with life. But, without doubt, from time to time they happen to miss their motherland.
That is why they keep taking part in ACM contests held in Russia both as contestants and as organizers. They also like to sit on a skyscraper roof beside a chimney, discuss latest news from Russia and simply get a little bit nostalgic. And it somehow naturally became a tradition to finish the "nostalgic evenings" with the Tunnel Towards Rutracker (TTR) table game.
A deck of cards of k+1 various colors (colors enumerated from 0 to k) is used in the game. Color 0 is special, this will be described further in the rules.
The game goes as follows. At first Sasha takes several cards in his hand and shows them to Slava. Then Slava shuffles the remaining deck and "blindly" gives Sasha t cards from the top. Only Sasha can see these cards. Next Slava sets and reads out two numbers x and y — parameters of the tunnel that Sasha will have to build.
In order to build a tunnel, Sasha looks at his cards and names a color color (1 ≤ colork) used for construction. After that Slava opens y top cards from the deck, selects all cards of colors 0 and color from them, and puts the selected cards on the table. Then Sasha repeats this procedure with the cards in his hand: selects all cards of colors 0 and color, and puts the selected cards on the table. Sasha wins if he puts on the table at least x cards more than Slava, otherwise he loses.
When choosing a color for construction Sasha, of course, decides in favor of the one that maximizes the probability of his win.
Slava got tired of setting x and y parameters randomly. Now before reading them out he wants to calculate the probability of Sasha’s win. It is known that Slava shuffles the cards fairly — all combinations are equiprobable. Slava also knows that Sasha employs the aferementioned strategy.


The first line contains two numbers k and t (1 ≤ k ≤ 100, 0 ≤ t ≤ 100) separated by space  — maximum possible color and the number of cards that Slava gave to Sasha "blindly".
The second line contains integers c0, …, ck, separated by space, where ci is the number of cards of color i in the deck (0 ≤ ci). Total number of cards in the deck does not exceed 100.
The third line contains integers s0, …, sk, separated by space, where si is the number of cards of color i which Sasha initially took in his hand in the beginning of the game (0 ≤ sici).
The fourth line contains two integer numbers x and y (0 ≤ x, y ≤ 100) separated by space  — tunnel parameters set by Slava.
It is guaranteed that there are not less than y cards left in the deck after Sasha receives all his cards.


Find the probability of Sasha’s win. Let the resulting probability be an irreducible fraction p/q, then output the number p·(q)−1 modulo 109+7.


3 1
1 2 0 1
0 1 0 0
1 2
2 3
6 5 3
2 2 0
5 3


In the first example Sasha may have the following sets of cards: {0, 1}, {1, 1} and {1, 3} (each variant has a probability of 1/3). Two more cards (i.e. all cards remaining in the deck) will be opened when building the tunnel. WIth any available combination Sasha will try to build the tunnel with cards of color 1, and in two cases of three he will succeed. Thus, the answer is 2/3.
Let’s look at the second example. Let’s take the case in which Sasha gets three cards of color 0. It will occur with a probability of 1/30. In this case he will choose color 1, because choosing color 1 gives a win probability of 31/35, and choosing color 2  — 1/35. In the case when Sasha gets 3 cards of color 2 (this will happen with a probability of 1/120), he will choose color 2, because choosing color 1 gives a win probability of 0, and choosing color 2  — 1/35. Having analyzed other combinations the same way, we get a total probability of 471/1400.
Problem Author: Eugene Kurpilyansky
To submit the solution for this problem go to the Problem set: 2088. Nostalgic Evening