1647 - パスワードをお忘れですか？

問題

二郎君は数式を用いたセキュリティシステムを開発した。システムにはa、b、c、dを変数とする数式が設定されており、それぞれに０から９までの整数を入力すると計算が行われる。その計算結果が正の整数N と一致したとき、ロックが解除される。ロックを解除できる４つの整数をa,b,c,dの順に並べた４桁の数字の列がパスワードになる。

二郎君はこのシステムで彼が使っているパスワードを忘れてしまった。幸い、二郎君はシステムに設定されている数式と、$N$ の値は覚えていたので、それを使ってパスワードを特定しようと考えた。

システムに設定されている数式と正の整数Nが与えられたとき、パスワードの候補の数を求めるプログラムを作成せよ。

入力

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

$S$
$N$

１行目にシステムに設定されている数式を表す文字列$S$が与えられる。2行目に、整数$N(1 \leq N \leq$ 10,000,000,000,000,000,000 = 10¹⁶

$S$は算術式を表す文字列であり、以下の要素から構成される。

• 加減乗算（それぞれ +, -, *）
• カッコ「(」または「)」
• 0から10,000までの整数
• 変数a,b,c,d
• 変数の連結

変数が連続して与えられた場合は変数の連結を表し、それらの変数の値を並べてできる一つの数とみなす。たとえば、a=0、b=1、c=2なら、abcは一つの整数12を表す。

また、$S$は以下の条件を満たす。

• 符号を反転する記号として演算子-が使われることはない。
• 乗算を表すときに演算子*が省略されることはない。
• Sの長さは200以下である。
• 乗算演算子*は２回までしか現れない。
• 変数が連続するのは４つまでである（たとえば、abcda, aaabb, aaaaaaのようなものは与えられない）。
• 空白文字は含まれない。
• 変数の連結を除いて、通常の数式である。

出力

パスワードの候補の数を１行目に出力する。パスワードがひとつに特定できる場合は、それを２行目に出力する。

入出力例

入力例1

a+b+c+d
36

出力例1

1
9999

入力例2

a+b+c+d
5

出力例2

56

式a+b+c+dが5になるのはa=b=c=0,d=5のときだが、他にもa=b=c=1,d=2などでも5になるので、合計で56通りの候補が存在する。

入力例3

b+c+d
27

出力例3

10

式b+c+dが27になるのはb=c=d=9のときだが、aの選び方は任意なので10通りの候補が存在する。

入力例4

abcd+abcd
1024

出力例4

1
0512

式abcd+abcdが1024になるのはa=0,b=5,c=1,d=2のときだけなので、候補は１つだけであり、0512が唯一のパスワードである。