묻고 더블로 마셔

시간 제한1초메모리 제한512 MB

요약

k+1번째 항부터 직전 k개 항의 합을 P로 나눈 나머지로 정의할 때, N번째 항의 값을 구한다. N은 최대 10^9이다.

문제

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

게임을 시작할 때 첫 번째, 두 번째, $\cdots$ , $k$ 번째 사람이 각자 마실 양을 정한다.
$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$ )

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