Description

The Epic of Gilgamesh is the first heroic epic in human history and one of the greatest literary works of Mesopotamia. It tells the legendary life story of Gilgamesh. In the anime Fate/stay night, Gilgamesh appears in the real world together with legendary heroes such as King Arthur, and a world-shaking battle begins. In the epic recorded on 12 clay tablets, Gilgamesh and his companion Enkidu subdue the guardian of the forest—the divine beast Humbaba—becoming the strongest king on earth, and at the same time taking all the treasures of the world for themselves. The “Gate of Babylon” becomes the capital that “Kinpika” (Gilgamesh’s nickname...) uses to show off in Fate...

One day, Kinpika suddenly has an idea: if he randomly takes out at most $M$ treasures from his endless collection to smash enemies to death, how many different ways of matching are there in total? Suppose Kinpika has $N$ different types of treasures. Most types have an unlimited quantity, but among them there are $T$ types of “super divine artifacts” whose quantities are limited. Let the quantity of the $i$-th super divine artifact be at most $B_i$. If the numbers of treasures of each type are the same, then they are considered the same matching plan.

Kinpika knows the number of plans will be very large. Since he has always been good at math, he chooses a prime number $P$. Please help him compute the remainder of the number of plans modulo $P$. Note that selecting none is also a valid plan.

Input Format

The first line contains four integers: $N$, $T$, $M$, $P$.

The next $T$ lines each contain one integer, representing $B_i$.

Constraints: $N, M \le 10^9$, $P \le 10^5$, $B_i \le 10^9$, $0 \le T \le N$, $M > 0$, $B_i > 0$, $T \le 15$.

Output Format

Output only one integer, the remainder of the number of plans modulo $P$.

2 1 10 13
3

12

Hint

There is only one super divine artifact, with quantity at most 3.

When not selecting the super divine artifact, the other type of treasure can be selected from 0 to 10 items, for a total of 11 plans.

When selecting 1 artifact, the other type of treasure can be selected from 0 to 9 items, for a total of 10 plans.

When selecting 2 artifacts, there are 9 plans in total.

When selecting 3 artifacts, there are 8 plans in total.

In total there are $11 + 10 + 9 + 8 = 38$ plans, and $38 \bmod 13 = 12$, so the answer is 12.

Translated by ChatGPT 5