二郎君は数式を用いたセキュリティシステムを開発した。システムにはa、b、c、dを変数とする数式が設定されており、それぞれに０から９までの整数を入力すると計算が行われる。その計算結果が正の整数$N$と一致したとき、ロックが解除される。ロックを解除できる４つの整数をa,b,c,dの順に並べた４桁の数字の列がパスワードになる。
二郎君はこのシステムで彼が使っているパスワードを忘れてしまった。幸い、二郎君はシステムに設定されている数式と、$N$の値は覚えていたので、それを使ってパスワードを特定しようと考えた。
システムに設定されている数式と正の整数Nが与えられたとき、パスワードの候補の数を求めるプログラムを作成せよ。
入力は以下の形式で与えられる。
$S$ $N$
１行目にシステムに設定されている数式を表す文字列$S$が与えられる。２行目に、整数$N$($1 \leq N \leq 10,000,000,000,000,000 = 10^{16}$)が与えられる。
$S$は算術式を表す文字列であり、以下の要素から構成される。
変数が連続して与えられた場合は変数の連結を表し、それらの変数の値を並べてできる一つの数とみなす。たとえば、a=0、b=1、c=2なら、abcは一つの整数12を表す。
また、$S$は以下の条件を満たす。
パスワードの候補の数を１行目に出力する。パスワードがひとつに特定できる場合は、それを２行目に出力する。
a+b+c+d 36
1 9999
a+b+c+d 5
56
式a+b+c+dが5になるのはa=b=c=0,d=5のときだが、他にもa=b=c=1,d=2などでも5になるので、合計で56通りの候補が存在する。
b+c+d 27
10
式b+c+dが27になるのはb=c=d=9のときだが、aの選び方は任意なので10通りの候補が存在する。
abcd+abcd 1024
1 0512
式abcd+abcdが1024になるのはa=0,b=5,c=1,d=2のときだけなので、候補は１つだけであり、0512が唯一のパスワードである。