방 번호

바이트 나라의 어느 호텔에 비밀 요원 피투시(Pituś)가 숨어 있습니다. 누군가 자신의 방 번호를 알아냈을까 걱정한 피투시는, 밤사이 방 번호에 적힌 숫자 가운데 일부 $9$를 $6$으로, 일부 $6$을 $9$로 몰래 뒤집어 놓았습니다.

피투시를 잡으러 온 요원 데이프(Dejf)는 피투시가 처음 배정받은 방 번호(뒤집기 전의 번호)와, $6$과 $9$가 뒤집혔다는 사실까지 알아냈습니다. 하지만 어느 자리의 숫자가 실제로 뒤집혔는지는 알 수 없습니다. 그래서 피투시를 확실히 찾으려면 방을 몇 개나 확인해야 하는지 고민하고 있습니다.

원래 방 번호 $n$에서 숫자가 $6$ 또는 $9$인 자리는 각각 $6$과 $9$ 중 어느 값으로도 바뀌어 있을 수 있고, 각 자리는 서로 독립적으로 정해집니다. 이렇게 만들 수 있는 서로 다른 방 번호 가운데, 호텔에 실제로 있는 방(번호가 $1$ 이상 $h$ 이하)의 개수가 데이프가 확인해야 하는 방의 개수입니다.

호텔의 방 개수 $h$와 원래 방 번호 $n$이 주어질 때, 데이프가 확인해야 하는 방의 개수를 구하세요. 그 개수를 $10^7 - 3$으로 나눈 나머지를 출력하면 됩니다.

첫째 줄에 호텔의 방 개수를 나타내는 정수 $h$ ($1 \le h \le 10^{1000000}$)가 주어집니다.

둘째 줄에 피투시가 처음 배정받은 방 번호를 나타내는 정수 $n$ ($1 \le n \le h$)이 주어집니다.

$h$와 $n$은 앞에 $0$이 붙지 않은 십진수로 주어지며, 자릿수가 매우 클 수 있습니다.

데이프가 확인해야 하는 방의 개수를 $10^7 - 3$으로 나눈 나머지를 한 줄에 출력하세요.