Note

この問題は No.295 hel__world を及びその想定解を元に作成されましたが、この出題により誤りの箇所が見つかりNo.295の問題文自体も修正されました。
(2017/12/03 02:50)問題文を修正いたしました。ご迷惑をおかけしました。

問題文

文字列$S$の連結成分の個数を、次の操作を行えるだけ行った後の文字列長さとして定めます。
操作：同じ文字が2文字以上連続する箇所があれば、そこから1文字取り除く
例えば「helloworld」の連結成分の個数は$9$、「aababbaaa」の連結成分の個数は$5$となります。

文字列 $S$ の $T$ 数を $S$ が含む部分列 $T$ の個数とします。
例えば、$S$ をhelloworld、$T$ をhelworld とすると、helloworldはhel__worldとhe_l_worldの2つを部分列として持つので、helloworld の helworld 数は $2$ です。

次の2条件を満たす文字列$S$に対する、$T$数の最大値を$\mathrm{mod}{10}^6+3$で求めてください。
・$S$に含まれる文字$alpha$の個数は高々$S_{alpha}$
・$S$の連結成分の個数と$T$の連結成分の個数は等しい
条件を満たすような文字列が存在しなければ0を出力してください。

入力

$S_a$ $S_b$ $S_c$ $S_d$ $S_e$ $S_f$ $S_g$ $S_h$ $S_i$ $S_j$ $S_k$ $S_l$ $S_m$ $S_n$ $S_o$ $S_p$ $S_q$ $S_r$ $S_s$ $S_t$ $S_u$ $S_v$ $S_w$ $S_x$ $S_y$ $S_z$
$T$

$0\le S_{alpha}\le {10}^{18}$ ( $alpha\in \{a,\cdots ,z\}$)
$1\le |T|\le {10}^6$
$S_{alpha}$ は、文字列 $S$ に文字 $alpha$ が 高々 $S_{alpha}$ 個含まれていることを表す。
文字列 $S$,$T$が含む文字は、$a,b,\cdots ,z$(小文字のアルファベット)のいずれかである。

出力

条件をみたすような$S$に対する最大の $T$ 数を$\mathrm{mod}{10}^6+3$で出力してください。（10^6+3は素数です）
最後に改行してください。

サンプル