주식을 안전하게 (Hard)

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

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

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

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

초깃값을 계산하기 위해 고려하는 기간(일)을 $p$라 한다. $1$일 차부터 $p - 1$일 차까지($1 \le n < p$)의 기준치는 실제 금액 변동량 $D_n = M_n - M_{n-1}$로 직접 계산한다. $p$일 차부터($n \ge 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 \le p \le 100$), $c$($1 \le c \le 100$), $k$($p \le k \le 10^{18}$)가 공백으로 구분되어 주어진다.

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

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

두 정수 $a$, $b$에 대해 $a = bq + r$ $(0 \le r < |b|)$를 만족하는 정수 $q$, $r$이 존재할 때, $r$을 $a$를 $b$로 나눈 나머지라고 한다.