Drink with Double or Fold

Youngsu and his $N-1$ friends invented a new drinking game called "Drink with Double or Fold". The game proceeds as follows.

1. At the start of the game, the first, second, $\cdots$, $k$-th person each decide how much to drink.
2. Starting from the $i$-th person ($i \geq k+1$), that person drinks an amount equal to the sum of what the $i-1, i-2, \cdots, i-k$-th people drank, taken modulo $P$.

Given the amounts $a_1, a_2, \cdots, a_k$ that the first $k$ people drink, and given that Youngsu drinks last, find the amount of alcohol Youngsu will drink. Youngsu and his friends have no limit on how much they can drink, so there is no need to worry about their health.

The first line gives $n$ and $k$. ($k < N \leq 10^9$, $1 \leq k \leq 100$)

The second line gives the amounts $a_1, a_2, \cdots, a_k$ that the first $k$ people drink, in order. ($1 \leq a_i \leq 10^9$)

The last line gives the integer $P$. ($1 \leq P \leq 10^9+7$)

Print the amount of alcohol Youngsu will drink.