23819번 - 묻고 더블로 마셔

문제

영수를 포함한 $N$명의 친구들은 새로운 술게임, "묻고 더블로 마셔"를 고안했다. 이 게임은 다음과 같이 진행된다.

1. 게임 시작 시 첫 번째, 두 번째, $\cdots,ドル $k$ 번째 사람은 본인이 마실 양을 정한다.
2. $i$ 번째($i \geq k+1$) 사람부터는 $i-1, i-2, \cdots, i-k$ 번째 사람이 마신 양의 합을 $P$로 나눈 나머지만큼 마신다.

첫 $k$명이 마시는 양이 각각 $a_1, a_2, \cdots, a_k$로 주어지고 영수가 마지막으로 마신다고 할 때 영수가 마시게 될 술의 양을 구하시오. 영수와 친구들은 주량이 무제한이기에 건강은 걱정하지 않아도 된다.

입력

첫 번째 줄에 $n,ドル $k$ $(k < N \leq 10^9,ドル 1ドル \leq k \leq 100)$가 주어진다.

두 번째 줄에는 최초 $k$명의 사람들이 마시는 술의 양 $a_1, a_2, \cdots, a_k$ $(1 \leq a_i \leq 10^9)$이 순서대로 주어진다.

마지막 줄에는 정수 $P$가 주어진다. (1ドル \leq P \leq 10^9+7$)

출력

영수가 마시게 될 술의 양을 출력한다.

제한

힌트