Room Numbers

A secret agent named Pituś is hiding in a hotel in Byteland. Worried that someone might have learned his room number, during the night he secretly turned some of the digit $9$s into $6$s and some of the $6$s into $9$s on his room number.

Agent Dejf came to catch Pituś. Dejf found out the room number that Pituś was originally assigned (the number before any flipping) and also learned that $6$s and $9$s had been flipped. However, he does not know which digit positions were actually flipped. So he is wondering how many rooms he must check to be certain of finding Pituś.

In the original room number $n$, every position holding a $6$ or a $9$ could now be either a $6$ or a $9$, and each such position is decided independently. Among all the distinct room numbers that can be formed this way, the ones that are actual rooms of the hotel (a number between $1$ and $h$ inclusive) are exactly the rooms Dejf must check.

Given the number of rooms $h$ and the original room number $n$, compute how many rooms Dejf must check. Print that count modulo $10^7 - 3$.

The first line contains an integer $h$ ($1 \le h \le 10^{1000000}$), the number of rooms in the hotel.

The second line contains an integer $n$ ($1 \le n \le h$), the room number originally assigned to Pituś.

Both $h$ and $n$ are given as decimal integers without leading zeros and may have a very large number of digits.

Print, on a single line, the number of rooms Dejf must check, taken modulo $10^7 - 3$.