There is a classic RPG called Pathmaker: Kingfinder, and you can't get enough of this game. Now you're challenging one of the most difficult lords in the game - the Goblin King.

Due to the drain from previous battles, you have blood points remaining and can only release two skills, which can attack and defend, respectively. Fortunately, these skills have enough remaining that you can consider them used an unlimited number of times. At any moment when your blood point is less than or equal to 0, you will die.

There are turns in total, each turn you act first and the Goblin King acts second. The Goblin King always attacks you once with damage of and one of the attributes fire, ice, wind, or earth, represented by a number . You can and can only unleash one of the two skills you have.

The attack skill always deals damage, but the probability of hitting varies from turn to turn. Taking into account complications such as movement and terrain limitations of both sides, this probability is in the turn.

The defense skill has limits , and it operates as follows: each time you are attacked, you first completely cancel out the damage you took this time, and then make a decision: if for a certain attribute , the XOR sum of the cumulative damage of that attribute already canceled by this skill is not less than , it will end immediately; otherwise it remains. Formally, this means that is satisfied. If you take a certain attack without a still valid defense skill, your blood will be reduced by . When you die, the entire round there after will not be played. Please notice that even if you have a defense skill still in effect , you can unleash one more defense skill. At this point the previous skill is considered to have ended early and the XOR and will start accumulating again.

You now want to know what is the maximum expected damage you can deal to a monster before turns are all over, or before you die. The answer is modulo .

The first row of three positive integers,  (), represents the number of rounds, the damage of the attack skill, and your blood level, respectively.

The second line of  positive integers, , represents the damage of the lord's attack on the  turn.

The third line,  positive integer , indicates the attribute of the  rounds of lord attacks.

The fourth line,  positive integer , represents the probability of hitting your attack skill in the  rounds. The exact probability  .

The fifth row of four positive integers, , expresses the  limit for the defense skill.

A positive integer on a line that represents the remainder of the maximum expected damage to the lord, modulo  .

4 1 1
1 2 3 2
0 0 0 1
1 1 10 10
3 1 10 10

1

3 10 5
4 9 1
0 0 0
20 0 10
1 9 9 9

15

In the second sample, you released attack skills and took four points of damage in the first round. You release the defense skill in the second round, and the defense skill ends in the same round. You died after attacking the enemy in the third round. This is allowed. It can be proved that you can cause the maximum expected damage in this situation.