配点 : $400$ 点

問題文

0 ～ 9 からなる文字列 $X$ と、整数 $M$ が与えられます。

$X$ に含まれる最も大きい数字を $d$ とします。

$d+1$ 以上の整数 $n$ を選んで $X$ を $n$ 進法表記の数とみなして得られる値のうち、$M$ 以下であるようなものは何種類あるでしょうか？

制約

• $X$ は 0 ～ 9 のみからなる
• $X$ の長さは $1$ 以上 $60$ 以下
• $X$ の先頭の文字は 0 ではない
• $1 \leq M \leq 10^{18}$

入力

入力は以下の形式で標準入力から与えられる。

$X$

$M$

出力

答えを出力せよ。

22
10

2

$X$ に含まれる最も大きい数字は 2 です。

• $X$ を $3$ 進法表記とみなして得られる値は $8$ です。
• $X$ を $4$ 進法表記とみなして得られる値は $10$ です。

得られる値のうち $10$ 以下のものはこの $2$ つのみです。

999
1500

3

$X$ に含まれる最も大きい数字は 9 です。

• $X$ を $10$ 進法表記とみなして得られる値は $999$ です。
• $X$ を $11$ 進法表記とみなして得られる値は $1197$ です。
• $X$ を $12$ 進法表記とみなして得られる値は $1413$ です。

得られる値のうち $1500$ 以下のものはこの $3$ つのみです。

100000000000000000000000000000000000000000000000000000000000
1000000000000000000

1

$X$ を $2$ 進法表記とみなして得られる $576460752303423488$ が、唯一の $1000000000000000000$ 以下の得られる数です。