リストは最初に数 $2, 3, \dots, n$ からなる。 ラウンドごとに、リスト中の最小の数をその二乗に置き換える。 最小の数が複数個ある場合は、そのうちの一つだけを置き換える。

例として、 $n=5$ の最初の3ラウンドを示す： $[2,3,4,5] \xrightarrow{(1)} [4,3,4,5] \xrightarrow{(2)} [4,9,4,5] \xrightarrow{(3)} [16,9,4,5]$

$m$ ラウンド後のリストの全ての数の和を $S(n,m)$ としよう。 例えば、$S(5,3) = 16 + 9 + 4 + 5 = 34$ である。 また $S(10, 100) \equiv 845339386 \pmod{1234567891}$ である。

$S(10^4, 10^{16}) \bmod 1234567891$ を求めよ。

リストは最初に数 $2, 3, \dots, n$ からなる。 ラウンドごとに、リスト中の全ての数をその最小の素因数で割る。 次に、それら最小の素因数の積を新たな数としてリストに追加する。 最後に、1になった数を全てリストから除く。

例として、 $n=5$ の最初の3ラウンドを示す： $[2,3,4,5] \xrightarrow{(1)} [2,60] \xrightarrow{(2)} [30,4] \xrightarrow{(3)} [15,2,4]$

$m$ ラウンド後のリストの全ての数の和を $S(n,m)$ としよう。 例えば、$S(5,3) = 15 + 2 + 4 = 21$ である。 また $S(10,100) = 257$ である。

$S(10^4, 10^{16}) \bmod 1234567891$ を求めよ。

（原題 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 のモジュロで入力せよ。