問題
うくさんは世界征服のために†最強の兵器†を作ることにしました。
$N$ 個の部品があります。部品それぞれには $1$ から $N$ の番号が振られていて, 部品 $i$ は数字 $A_i$ が $B_i$ 個並んだ値で表されます。
兵器は, $N$ 個すべての部品を好きな順番で連結することによって作られます。
兵器を作るためには, 連結後の値のぶんだけコストがかかります。ここで $0$ 以外の値で $0$ から始まる値は認めないこととします。
21:25 追記: $0$ を表すためには単一の $0$ のみしか認められません。($00$ や $000$, $0000000$ となるような入力は与えられないことが保証されます)。
魔界通販でお金を使いすぎたうくさんは, コストをなるべく小さくしたいと考えました。
兵器を作るためのコストの最小値と, 最小値にするための部品の連結する順番の組み合わせをそれぞれ $10^9 + 7$ で割った余りで求めてください。
入力
$N$ $A_1$ $B_1$ $A_2$ $B_2$ $:$ $A_N$ $B_N$
$1$ 行目には, 部品の個数 $N(1 \le N \le 10^5)$ が与えられます。
つづく $N$ 行のうち $i$ 行目には, $A_i, B_i(0 \le A_i \le 9, 1 \le B_i \le 10^9)$ が与えられます。 これは部品 $i$ について数字 $A_i$ が $B_i$ 個並んだ値であることを意味します。
条件を満たす連結の組み合わせが $1$ 通り以上ある入力が与えられることが保証されます。
出力
$1$ 行目に, コストの最小値を $10^9 + 7$ で割った余りで出力してください。
$2$ 行目に, 最小値にするための部品の連結する順番の組み合わせを $10^9 + 7$ で割った余りで出力してください。
入出力例
入力例 1
4 1 1 3 1 3 1 3 1
出力例 1
1333 6
$1333$ が最小値です。 このとき, 部品を連結する順番は以下の 6 通りです。
- $1 \to 2 \to 3 \to 4$
- $1 \to 2 \to 4 \to 3$
- $1 \to 3 \to 2 \to 4$
- $1 \to 3 \to 4 \to 2$
- $1 \to 4 \to 2 \to 3$
- $1 \to 4 \to 3 \to 2$
入力例 2
5 5 2 7 1 0 5 0 3 5 1
出力例 2
999997064 2
$500000000557$ が最小値で, これを $10^9 + 7$ で割った余りで出力します。
$000000005557$ などの値は $0$ から始まるため, 認められないことに注意してください。
また連結する順番としては $5 \to 3 \to 4 \to 1 \to 2, 5 \to 4 \to 3 \to 1 \to 2$ の $2$ 通りが考えられます。
入力例 3
1 0 1
出力例 3
0 1