코드 복원하기

달구의 프로그램은 $0$에서 $9$까지의 숫자로만 이루어진 코드를 비밀번호로 이용한다. 사용자의 보안을 위해, 달구의 프로그램은 길이 $N$의 비밀번호 $s$에 대해 $a\_i = h(s\_is\_{i+1}\cdots s\_{i+L-1})$로 해싱하여 만든 수열 $a\_1$, $a\_2$, $\cdots$, $a\_{N-L+1}$을 파일에 저장한다.

이때, $s\_is\_{i+1}\cdots s\_{i+L-1}$은 $s$의 $i$ 번째 숫자 부터 $i+L-1$ 번째 숫자까지를 이어 붙인 문자열이며, 어떤 숫자로만 이루어진 문자열 $t$에 대한 해시 함수 $h(t)$는 다음과 같다.

$h(t) = \sum\_{i=1}^{|t|}{t\[i] \times 17^{(|t|-i)}} \pmod{10^9+7}$

$t\[i]$는 $t$의 $i$번째 문자이다. 문자 0, 1, 2, $\cdots$, 9는 각각 정수 $0$, $1$, $2$, $\cdots$, $9$ 로 대응된다.

모든 수열과 문자열의 인덱스는 $1$부터 시작한다.

이 방식이 안전하다고 생각하는 달구를 위해 코드를 복원해보자.

첫째 줄에 정수 $N$과 $L$이 공백으로 구분되어 주어진다. ($1 \le N \le 100\\,000$; $1 \le L \le \lfloor \displaystyle\frac{N}{2}\rfloor$)

둘째 줄에 수열 $a\_1$, $a\_2$, $\cdots$, $a\_{N-L+1}$이 공백으로 구분되어 주어진다. ($0 \le a\_i \lt 10^9+7$)

비밀번호를 복원할 수 있는 수열만 입력으로 주어진다.

첫째 줄에 복원한 달구의 비밀번호를 출력한다.

복원 가능한 비밀번호가 여러 개 존재할 경우 사전순으로 가장 앞서는 비밀번호를 출력한다.