33852번 - PNUPC 1K9

문제

10ドル$진수는 0ドル$에서 9ドル$까지 숫자를 사용해 수를 나타내지만 진법에 따라서 알파벳을 사용하기도 한다. 예를 들어 16ドル$진수는 A부터 F까지 6개의 알파벳을 10ドル$부터 15ドル$까지 나타내는 데 사용해 수를 표기할 수 있다. 10ドル$진수 95는 16ドル$진수로 5F와 같이 표기할 수 있다. 36ドル$진수는 A부터 Z까지 26개의 알파벳을 10ドル$부터 35ドル$까지 나타내는 데 사용해 수를 표기할 수 있다. 10ドル$진수 71은 36ドル$진수 1Z와 같이 표기할 수 있다.

36ドル$진수로 표기된 양의 정수 $s$와 10ドル$진수로 표기된 양의 정수 $k,ドル $p$가 주어질 때 $s$의 자릿값을 수정해 $s \equiv k \pmod {p}$가 성립하도록 해 보자. 자릿값을 수정할 때 길이를 늘이거나 줄일 수 없으나 가장 큰자리 숫자를 0ドル$으로 수정할 수도 있다.

입력

첫 번째 줄에 36진수로 표기된 양의 정수 $s$가 주어진다. (1ドル \leq s < 36^{100 ,円 000}$)

두 번째 줄에 10진수로 표기된 양의 정수 $k,ドル $p$가 공백으로 구분되어 주어진다. (0ドル \leq k < p \leq 1,円 000$)

출력

$s \equiv k \pmod {p}$를 만족하게 하는 최소 수정 횟수를 출력한다. 만약 어떤 방법으로도 만족하게 할 수 없다면 대신 -1을 출력한다.

제한

노트

36진수 1K9는 10진수로 2025$(1 \times 36^2 + K \times 36 + 9)$이다.