828：テンパズル

（原題 Numbers Challenge）

いくつかの数から、目標の数を計算で作る問題は、よく知られた娯楽である。この問題では、6つの数と目標の数が与えられる。

例えば、6つの数 2, 3, 4, 6, 7, 25 と目標の数 211 が与えられたとき、一つの解は：

$211 = (3 + 6) \times 25 - (4 \times 7) \div 2$

これは6つの数を全て使っている。しかし、そうする必要はない。7を使わない別解がある：

$211 = (25 - 2) \times (6 + 3) + 4$

解に対して、そこで使った数の和をそのコストと定義する。上記の例題では、示した二つの解はそれぞれコスト47と40である。この例題はコスト40未満の解は存在しないことがわかる。

計算をするとき、以下の規則を守る必要がある：

• それぞれの数はたかだか一度しか使えない

• 基本の四則演算 $+, -, \times, \div$ のみが使える

• 全ての中間結果も正の整数でなければならない。よって例えば $3 \div 2$ は部分式として許されない（たとえ最終結果が整数になっても）

入力データ p828_number_challenges.txt には200の問題が含まれている。1行に1問で以下の形式に従う：

211:2,3,4,6,7,25

ここで、コロンの前の数が目標で、残りの、コンマ区切りの数が使用できる数である。

問題に $1,2,\dots,200$ と番号を順に振り、$n$番目の問題の解の最小コストを $s_n$とする。例えば、上記の例題はファイル中の最初の問題なので $s_1 = 40$ である。全ての問題が解を持つ訳ではないことに注意せよ。その場合は $s_n = 0$ とする。

$\displaystyle \sum_{n=1}^{200} 3^n s_n$ を求めよ。答えは 1005075251 のモジュロで入力せよ。