Восстановление числа

면접 대비

시간 제한2초메모리 제한1024 MB

요약

일부 자리가 물음표로 가려진 숫자 문자열과 정수 m이 주어질 때, 물음표를 숫자로 바꿔 만들 수 있는 수 중 m으로 나눈 나머지의 최솟값을 구한다. 맨 앞자리가 0이면 안 된다.

난이도: 보통10점 중 5점
유형: 완전 탐색, 동적 계획법, 수학, 구현
정답자: 아직 제출이 없습니다

문제

Мистер Саламандер едет в поезде. Он записал два числа $n$ и $m$ и отлучился. Когда он вернулся, оказалось, что его чай залил некоторые цифры числа $n$ .

Мистер Саламандер любит головоломки, поэтому ему стало интересно: какой наименьший остаток от деления на $m$ могло давать исходное число $n$ ?

Вам дана строка, представляющее залитое число $n$ , в которой на каждой позиции находится либо цифра, либо знак вопроса, обозначающий, что данная цифра залита чаем, и модуль $m$ .

입력

В первой строке находится непустая строка $n$ и натуральное число $m$ --- модуль ( $1 \le m \le 10^9$ ). Cтрока $n$ состоит из цифр и знаков вопроса, не имеет ведущих нулей, и ее длина не превосходит $14$ .

출력

В единственной строке выведите наименьший остаток от деления, который можно получить, заменив знаки вопросов на цифры, так, чтобы получившееся число не имело ведущих нулей.

예제3

예제 1
입력
```
3?1? 3215
```
예상 출력
```
0
```
예제 2
입력
```
?? 20
```
예상 출력
```
0
```
예제 3
입력
```
?1? 730
```
예상 출력
```
80
```