에니그마

코르넬리우스 바커는 해적이면서 천문학자이자 수학자였다. 그는 재산 대부분을 카리브해의 세인트바실 섬에 묻었는데, 그 섬에서는 피코콜롬보 봉우리를 기준점으로 삼는다. 바커는 1617년에 배 세 척이 허리케인에 휩쓸리면서 자취를 감췄다. 마지막 항해에 나서기 전, 바커는 네덜란드에 있는 조카에게 편지를 보내 피코콜롬보에서 정남쪽으로 보물까지 가는 정확한 거리를 적어 두었다.

편지가 도둑의 손에 들어갈까 걱정한 바커는 거리를 그대로 쓰지 않았다. 거리에 다른 수 $N$을 곱한 결과 $D$를 적고, $N$의 값과 자신이 한 계산 방법을 함께 남겼다. 그 시절 도둑 중에 두 수를 나눌 줄 아는 사람은 거의 없었다. 편지는 유럽에 도착했지만, 조카는 이미 수녀원에 들어간 뒤라 봉투를 열어 보지도 않았다.

정확히 400년 뒤, 마리아는 그 수녀의 유품이 든 궤짝을 물려받았고 뜯지 않은 편지를 발견했다. 마리아는 보물을 찾아 떠날 계획이다. $N$은 그대로 읽을 수 있지만 $D$는 좀이 갉아먹어 일부 자리가 지워졌다. 남은 단서는 $D$의 맨 앞자리가 0이 아니라는 사실뿐이고, 바커가 편지에 그렇게 적어 두었다.

훼손된 $D$의 모양과 $N$이 주어질 때, 조건을 만족하는 $D$ 중 가장 작은 값을 구하라.

첫째 줄에 문자열 $S$와 정수 $N$ ($1 \le N \le 1000$)이 공백으로 구분되어 주어진다. $S$는 비어 있지 않고 길이가 1000 이하이다. $S$의 각 문자는 숫자이거나, 좀이 갉아먹은 자리를 뜻하는 물음표 ?이다. $S$의 첫 문자는 0이 아니고, 물음표는 적어도 한 개 있다.

자릿수가 정확히 $|S|$이고, $N$의 배수이며, 맨 앞자리가 0이 아니고, $S$에 숫자가 적힌 모든 자리에서 그 숫자와 일치하는 정수 $D$를 생각한다. 이런 $D$ 중 가장 작은 값을 한 줄에 출력한다. 그런 $D$가 하나도 없으면 별표 * 한 개만 출력한다.