G問題 - 114514-like number

実行時間制限: 2sec / メモリ制限: 1024MB

問題文

各桁が1,4,5のいずれかからなり、かつ1,4,5の3種類の数字すべてがいずれかの桁に現れるような正の整数を114514-like numberと呼ぶことにします。例えば114514や541は114514-like numberですが、111や1450は114514-like numberではありません。

小さい方から\(N\)番目の114514-like number\(X\)が与えられるので、\(N\)を114514で割った余りを出力してください。

制約

• \(1 \leq X \leq 10^{200000}\)
• \(X\)は114514-like number
• 入力はすべて整数で与えられる。

入力

X

小さい方から\(N\)番目の114514-like number\(X\)が1行で入力される。

出力

N

\(N\)を114514で割った余りを1行で出力してください。

入力例1

1145

出力例1

7

114514-like numberを小さい順に並べると、145,154,415,451,514,541,1145となるので、1145は7番目の114514-like numberです。7を114514で割った余りは7なので7を出力します。

入力例2

1144454

出力例2

810

1144454は810番目の114514-like numberです。

入力例3

114514

出力例3

216

114514は216番目の114514-like numberです。

入力例3

4551114154444115114551554411514544544

出力例3

111173