Thor vs Superman vs Goku
One of the biggest arguments between comic and anime fans is the topic of Superman vs Goku. Another famous strong superhero from Marvel to rival them is Thor. You have decided to find the answer to 'Thor vs Superman vs Goku' once and for all by doing your final year thesis research on this grand vs-battle-scenario.
One part of your research is gauging their strength against other enemies, in this case, Pokémon! RUET is full of wild Pokémon. So, you have invited Thor, Superman and Goku to RUET and asked them to help you on your research. There are N Pokémon in RUET, some of them are stronger than the heroes while some of them are weaker. The energy level of each Pokémon is already known to you.
Each hero also has an energy level, an integer number from 1 to max energy of the hero. The max energy levels of Thor, Superman and Goku are respectively MT, MS and MG. So, at any moment, Thor's energy level may be an integer in the range [1, MT] and so on for the other heroes as well.
Now, you have asked the heroes to battle continuously for T minutes. In each minute, each of them will battle a single Pokémon. When a hero battles a stronger Pokémon (the Pokémon has more energy level than the hero), his energy level will decrease. If he battles a weaker Pokémon (the Pokémon has less energy level than the hero), his energy level will increase. If their energy levels are the same, hero's energy after battle stays the same too. There is no guarantee on how much energy a hero might lose or gain. So, for example, if you see Goku's energy level increase after a battle, it is guaranteed that Goku battled a Pokémon weaker than him and it can be any of the Pokémon that had less energy level than Goku's previous energy level.
For each battle, you take a photo. So this kind of photo will have two characters, one of the heroes and one of the Pokémon. Two photos are the same when they contain exactly same characters, for example, all photos containing Goku and a specific Pokémon of RUET are considered the same photo. After a battle, you also take a photo of the hero himself with his current energy level written on top of the photo. Two such photos with only a single hero in them are the same when the photos have the same numbers written on them.
You are making a photo album for your research. The first 3 photos are - a photo of Thor with his initial energy level (IT) written on it, a photo of Superman with his initial energy level (IS) written on it and a photo of Goku with his initial energy level (IG) written on it.
Then for each minute, you first add a photo of Thor battling a random Pokémon followed by a photo of Thor with his current energy level. Then you do the same for Superman, and then for Goku.
Now you are wondering, if you already know T, IT, IS, IG, MT, MS, MG, N, energy levels of all N Pokémon , Thor's final energy level after T minutes (UT), Superman's final energy level after T minutes (US) and Goku's final energy level after T minutes (UG), what is the number of distinct photo albums can you get?
Note, two photo albums are the same if they have the same photos in each position. A Pokémon doesn't faint or go away after a battle, it stays the same. That means, a hero can battle the same Pokémon in different minutes. Furthermore, the heroes don't battle at the same time. First Thor battles, then Superman, then Goku, in the same minute. So, it is possible that more than one of them can fight battles against the same Pokémon at the same minute e.g. if Superman battles against a specific Pokémon in i-th minute, Goku or Thor might battle that same Pokémon in i-th minute as well.
Input
In each input file, you are given two integers T and N in the first line. The next line contains 3 integers IT, IS and IG respectively.
The following line contains UT, US, UG.
Then MT, MS, MG are given in another line.
And finally the last line of the input contains N 32-bit integers, each denoting the energy level of a Pokémon.
1 ≤ T ≤ 5∗106
1 ≤ MT∗MS∗MG ≤ 200
1 ≤ IT, UT ≤ MT
1 ≤ IS, US ≤ MS
1 ≤ IG, UG ≤ MG
1 ≤ N ≤ 104
Output
Print the number of distinct photo albums that you can obtain. Since the answer can be large, print it modulo 109+7
Samples
| Input | Output |
|---|---|
1 2 1 3 1 1 4 1 1 4 1 1 2 | 2 |
| Input | Output |
|---|---|
1 5 2 2 1 1 3 1 2 3 1 1 1 2 2 3 | 4 |
| Input | Output |
|---|---|
1 5 1 2 1 1 3 1 2 3 1 1 1 1 2 3 | 27 |
| Input | Output |
|---|---|
2 5 1 2 1 1 1 1 1 3 1 1 1 2 2 3 | 64 |
In the first sample case, T = 1 i.e. only one minute has passed. The photo album here will consist of 9 photos and starts with 3 photos corresponding to the initial energies [Thor, 1], [Sup, 3], [Goku, 1]. The album ends with 3 fixed photos as well: [Thor, 1], [Sup, 4], [Goku, 1]. These 3 positions are fixed. For the middle 3 photos, the photo of Thor has only one option as there is only one Pokémon equal to Thor. Same for Goku. But there are 2 Pokémon weaker than Superman, so there are 2 options here.
So overall, there can be 2 distinct photo albums and thus output is 2.
The 2 albums can be represented as
[Thor, 1], [Sup, 3], [Goku, 1], [Thor, P1], [Sup, P1], [Goku, P1], [Thor, 1], [Sup, 4], [Goku, 1]
and
[Thor, 1], [Sup, 3], [Goku, 1], [Thor, P1], [Sup, P2], [Goku, P1], [Thor, 1], [Sup, 4], [Goku, 1]
where [Thor, 1] represents to a photo of Thor with energy level 1 and [Sup, P2] represents a photo of Superman battling with 2nd Pokémon stronger than him.
