29817번 - 주식을 안전하게 (Hard)

문제

주의: 주식을 안전하게(Hard) 문제는 주식을 안전하게(Easy) 문제와 구해야 하는 값이 다르다.

요즘 김한양의 최대 관심사는 주식이다. 7번 연속 주식 투자에 실패했지만, 이번에는 성공할 수 있도록 직접 주식 자동 매매를 할 수 있는 인공지능을 개발했고, 이 인공지능이 김한양을 대신해서 주식 투자를 할 예정이다.

주식 거래를 위해 개설한 통장에는 매일 임의의 금액(원)이 담겨 있다. 0ドル$일 차 초기 금액 $M_0$부터 시작하여 인공지능이 주식 투자를 한 지 $n$($n≥1$)일 차가 되었을 때 통장에 있는 금액(원)을 $M_n$이라 하자. 편의상 통장에서 매일 얻거나 잃을 수 있는 금액에는 제한이 없고, 금액이 음수라면 그만큼 빚이 있는 것으로 생각한다.

김한양은 인공지능을 완전히 믿지 않는다. 혹여나 인공지능이 실수한다면 큰 손실이 일어날 수도 있으므로 인공지능이 안전하게 투자했는지 확인할 수 있는 기준을 세웠다. 당일을 기준으로, 오늘 통장에 있는 금액에서 어제 통장에 있었던 금액을 뺀 값을 금액 변동량이라 할 때, 김한양은 이 금액 변동량이 특정한 기준치 이상일 때만 인공지능이 당일에 안전하게 주식 투자를 했다고 생각하기로 정했다. $n$일 차에서의 이 기준치를 $D_n$이라 할 때, 김한양은 $D_n$의 값을 다음과 같이 계산할 것이다.

초깃값을 계산하기 위해 고려한 기간(일)을 $p$라 할 때, 1ドル$일 차부터 $p - 1$일 차까지 $n(1≤n<p)$일 차에서의 기준치는 실제 금액 변동량인 $D_n = M_n - M_{n-1}$로 직접 계산한다. 이후 $p$일 차부터 $n(n≥p)$일 차에서의 기준치 $D_n$은 잠재적인 이익 및 손실의 비율을 나타낸 상수 $c$에 대하여 다음 등식을 만족시키는 값으로 계산한다.

$$D_n + c \times D_{n-1} + \dots + c^{p-1} \times D_{n+1-p} = 0$$

김한양의 경제학과 친구 한누리는 김한양이 만든 이 기준만으로는 인공지능이 안전하게 주식 투자를 하고 있는지 확인할 수 없다고 생각한다. 이를 김한양에게 설명하기 위해 $k$일차의 기준치 $D_k$의 값을 직접 계산하는 프로그램을 여러분의 도움을 받아 만들었다.

그러나 한누리는 이 프로그램만 가지고 김한양에게 설명하기에는 아직 부족하다고 느꼈다. 이번에는 인공지능이 안전하게 주식 투자를 한 지 $k$일 차일 때, 통장에 남은 금액인 $M_k$의 최솟값을 계산하는 프로그램이 필요하다. 한누리를 또 도와주자!

입력

첫 줄에는 세 정수 $p(2≤p≤100),ドル $c(1≤c≤100),ドル $k(p≤k≤10^{18})$가 공백을 사이로 해서 주어진다.

다음 줄에는 0ドル$일 차부터 $p-1$일 차까지 각 일 차마다 통장에 있는 금액을 나타내는 $p$개의 정수 $M_0, \dots, M_{p-1}(-10^8≤M_i≤10^8)$이 공백을 사이로 해서 주어진다.

출력

인공지능이 안전하게 주식 투자를 한 지 $k$일 차일 때, 통장에 남은 금액인 $M_k$의 최솟값을 10ドル^9+7$로 나눈 나머지를 출력한다.

제한

노트

두 정수 $a,ドル $b$가 임의의 두 정수 $q,ドル $r$에 대하여 $a = bq + r$ $(0≤ r < |b|)$로 표현할 수 있을 때, $r$을 $a$를 $b$로 나눈 나머지라고 한다.