BOJ 29817 주식을 안전하게 (Hard)

문제 링크:

문제 내용

길이 $p$의 수열 $M_0, M_1, \cdots, M_{p-1}$이 주어집니다. $i \ge 1$에 대해 $D_i = M_i - M_{i-1}$이라고 할 때, 상수 $c$에 대해 다음의 식이 성립하도록 수열 $M$을 연장하려고 합니다.

이때 $M_k$를 $10^9+7$로 나누었을 때의 음이 아닌 나머지를 구하세요.

입력

첫 줄에 $p$, $c$, $k$가 주어집니다. ($2 \le p \le 100$, $1 \le c \le 100$, $p \le k \le 10^{18}$

다음 줄에 $M_0, M_1, \cdots, M_{p-1}$이 주어집니다. ($-10^8 \le M_i \le 10^8$)

출력

문제의 정답을 출력합니다.

문제 풀이