Counting Artifact Combination Schemes

Problem Statement

Gilgamesh is the hero of the first epic in human history and one of the finest literary works of the Two Rivers. In the anime Fate/stay night, Gilgamesh (also known as Gold Picard) appears alongside legendary heroes such as King Arthur in a breathtaking battle. According to the epic recorded on 12 clay tablets, Gilgamesh, together with his comrade Angidu, subdues the forest guardian—the divine beast Hongbabah—and becomes the mightiest king on earth, collecting every treasure in the world. His "Gate of Babylon" becomes a symbol of his swagger in Fate...

One day, Gold Picard comes up with an idea: what if he randomly selects no more than M artifacts from his endless treasure trove to crush his enemies? He has N different types of artifacts in total. Most artifact types are available in unlimited quantities, but among them, there are T types of super-artifacts whose quantities are limited. For the i^th super-artifact, at most \(B_i\) items can be chosen. Note that if the numbers chosen for each type are the same, the overall combination is considered identical.

Count the number of possible selection schemes modulo a given prime P. Selecting no artifact at all is also considered a valid scheme.

Mathematical Formulation

Let \(x_1, x_2, \dots, x_N\) denote the number of items chosen from each artifact type. For the super-artifact types (assume these are the first \(T\) types), we have \(0 \le x_i \le B_i\) for \(1 \le i \le T\). For the remaining \(N-T\) types, the supply is unlimited (but note that the sum of all chosen items must not exceed \(M\)). The total number of items chosen must satisfy:

\[ x_1 + x_2 + \cdots + x_N \le M. \]

The answer is the total number of nonnegative integer solutions under these constraints, computed modulo P.

inputFormat

Input Format

• The first line contains four integers: \(N\), \(M\), \(T\), and \(P\) where \(P\) is a prime number.
• If \(T > 0\), the second line contains \(T\) integers: \(B_1, B_2, \dots, B_T\), representing the maximum available quantities for the super-artifact types.

It is guaranteed that \(0 \le M\), \(0 \le T \le N\), and for each \(i\), \(B_i \ge 0\).

outputFormat

Output Format

Output a single integer, the number of valid selection schemes modulo \(P\).

sample

3 2 1 7
1

2