003 - repdigit

時間制限 1 秒 / メモリ制限 256 MB / 得点 100 / x 17 /


TLE
1sec
MLE
256MB
得点
100

問題

うくさんは世界征服のために†最強の兵器†を作ることにしました。

$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