Burning Sceptre

In this problem, you are given two heroes and some soldiers in a game. The hero of player C (we call him your hero) has x life points, whereas the enemy hero has y life points. In addition, there are k soldiers with life points a₁, a₂, \dots, a_k.

You have a skill called the "Burning Sceptre". When used, the skill repeatedly performs the following procedure:

• Every time, it uniformly and randomly selects one alive character (either hero or soldier) and deals 10 points of damage to that character.
• If after subtracting 10, the life points of that character become \( \le 0 \), the character dies and will not be selected again.
• The process repeats until at least one hero dies. (Note that there are two heroes.)

Your task is to calculate the probability that the enemy hero dies (i.e. your hero survives) once the skill completes. To avoid precision issues, if the probability is represented as a rational number \( \frac{A}{B} \) in lowest terms, you are required to output \( A \times B^{-1} \bmod p \), where \( p \) is a given prime number and \( B^{-1} \) is the modular inverse of \( B \) modulo \( p \).

Important details:

• The effective number of hits needed to kill a character is the ceiling of its life points divided by 10. That is, for a life value \( L \), the number of hits required is \( \lceil \frac{L}{10} \rceil \).
• The process stops immediately when one of the heroes is killed.

All formulas above must be rendered in \( \LaTeX \) format (for example, \( x \) and \( \frac{A}{B} \)).

inputFormat

The input is given in two lines.

The first line contains four integers: x, y, k, and p where:

• \( x \) is the life points of your hero.
• \( y \) is the life points of the enemy hero.
• \( k \) is the number of soldiers.
• \( p \) is a prime number (the modulus).

The second line contains \( k \) integers: a1, a2, ..., ak representing the life points of each soldier.

Remember that the effective hit count for any character is \( \lceil \frac{\text{life}}{10} \rceil \).

outputFormat

Output a single integer representing the probability that the enemy hero dies (and your hero survives) modulo \( p \). That is, if the probability is \( \frac{A}{B} \) in lowest terms, print \( A \times B^{-1} \bmod p \), where \( B^{-1} \) is the modular inverse of \( B \) modulo \( p \).

sample

20 30 1 1000003
10

436695