[F] Functional Sequence

하바는 최근 학교에서 수열과 함수에 대해 배웠다. 배운 것을 바로 적용하는 성격의 하바는 아래와 같이 길이 $N$의 수열 $A$를 받아서 길이 $N$의 수열 $D$를 반환하는 함수 $d(A)$를 만들었다.

• $D_0=A_0$이다.
• $0<i<N$인 $i$에 대해 $D_i=A_{i}-A_{i-1}$이다.

하지만 이 함수를 가지고 놀던 하바는 함수를 여러 번 적용할 수 있다는 것을 깨닫고, 아래와 같이 길이 $N$의 수열 $A$를 받아서 길이 $N$의 수열 $B$를 반환하는 함수 $f(A)$를 만들었다.

• $0\le i<N$인 $i$에 대해 $B_{i}=(d^{i}(A))_i$이다.

$d^i$가 무엇을 의미하는지 모른다면 하단의 노트를 참고하자.

이제 조금 더 재밌는 함수를 가진 하바는 가지고 있던 수열 $A$에 함수 $f$를 $K$번 적용하여 $B=f^{K}(A)$를 만들었다.

수열 $B$와 함수를 적용한 횟수 $K$가 주어질 때 하바가 가지고 있던 수열 $A$를 추정해 보자.

첫째 줄에는 하바가 만든 수열 $B$의 길이 $N$과 하바가 함수를 적용한 횟수 $K$가 공백으로 구분되어 주어진다. $(1 \le N \le 5\,000;$ $0 \le K \le 10^9)$

둘째 줄에는 수열 $B$의 원소 $B_0$, $B_1$, $\ldots$, $B_{N-1}$이 공백으로 구분되어 주어진다. $(0 \le B_{i} \le 10^9)$

만약 조건을 만족하는 수열 $A$가 존재하지 않는다면 첫째 줄에 -1을 출력한다.

만약 조건을 만족하는 수열 $A$가 존재한다면 첫째 줄에 수열 $A$의 각 원소 $A_0$, $A_1$, $\ldots$, $A_{N-1}$을 $10^9 + 7$로 나눈 나머지를 공백으로 구분하여 출력한다.

만약 가능한 수열이 여러 가지라면 그중 아무거나 하나를 출력한다.

어떠한 함수 $f$에 대해 $f^{n}$은 다음과 같이 정의한다.

• $f^{0}(X) =X$다.
• $f^{n}(X) =f(f^{n-1}(X))$다.