009 - パスワードをお忘れですか?

時間制限 1 秒 / メモリ制限 64 MB / 得点 12 / x 0 /


TLE
1sec
MLE
64MB
得点
12

問題

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

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

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

入力

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

$S$
$N$

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

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

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

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

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

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

出力

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

入出力例

入力例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のときだけなので、候補は1つだけであり、0512が唯一のパスワードである。