Menteur-Hxy's Black Problem Challenge

Menteur-Hxy is determined to solve NOIp’s notorious black problems in order to achieve his target of AC-ing 100 hard problems before the contest. In order to do so, he decides to hire some "water soldiers" (cheaters), and he must hire at least one.

Each water soldier has an ability value \(x_i\), which means he is capable of solving a problem with difficulty up to \(x_i\). Once he solves a problem, he will always give it the highest possible rating. More precisely, based on his ability \(x_i\), his vote is determined as follows:

[ v(x_i)=\begin{cases} 1,&1\le x_i\le5,\ 10,&6\le x_i\le12,\ 15,&13\le x_i\le20,\ 25,&21\le x_i\le35,\ 40,&36\le x_i\le45,\ 55,&46\le x_i\le70,\ 100,&71\le x_i\le100. \end{cases} ]

Normal users will also vote on the problem. Their votes (which are one of the fixed scores {1, 10, 15, 25, 40, 55, 75, 100}) are given as input without any modification.

The final rating of the problem is computed as follows. Let the combined vote list (from normal users and the chosen water soldiers) be formed. Remove exactly one highest score and one lowest score, then take the average of the remaining votes. The problem is considered a black problem if the final average is within the black difficulty range \([71,100]\) (note that the black difficulty corresponds to scores from 71 to 100).

Given the water soldiers' ability values and the normal users' voting record, count the number of ways to choose a non-empty subset of water soldiers (i.e. at least one water soldier) such that the final computed average (after removing one minimum and one maximum vote) falls in the interval \([71,100]\). Since the answer may be huge, output it modulo \(p\).

Scoring Details

The rating is computed by first combining the votes from normal users and the water soldiers. Let the normal users' votes be \(A\) with sum \(S_A\), minimum \(L_A\) and maximum \(H_A\), and let the water soldiers' votes (when chosen) be \(B\) with sum \(S_B\), minimum \(L_B\) and maximum \(H_B\). Define the overall minimum \(L = \min(L_A, L_B)\) and overall maximum \(H = \max(H_A, H_B)\). If the total number of votes is \(T = m + k\) (where \(m\) is the number of normal votes and \(k\) the number of water soldiers chosen), then the final average is computed as:

[ \text{average} = \frac{S_A + S_B - L - H}{T - 2}. ]

Your task is to count the number of non-empty subsets of water soldiers for which this computed average satisfies

[ 71 \leq \frac{S_A + S_B - L - H}{T - 2} \leq 100. ]

inputFormat

The input consists of multiple lines:

1. The first line contains an integer \(n\) denoting the number of water soldiers.
2. The second line contains \(n\) space-separated integers \(x_1, x_2, \ldots, x_n\) representing the ability values of the water soldiers.
3. The third line contains an integer \(m\) indicating the number of normal users' votes.
4. The fourth line contains \(m\) space-separated integers, each being one of the possible vote scores, representing the normal users' votes.
5. The fifth line contains an integer \(p\) for modulo operation.

outputFormat

Output a single integer, the number of valid ways to choose a non-empty subset of water soldiers such that after adding their votes and computing the average (after removing one highest and one lowest vote), the average lies in the range \([71,100]\). Print the answer modulo \(p\).

sample

2
7 20
3
25 15 55
1000000007

0