問題文

$1$ 桁の正整数が $N$ 個あります．このうち $i$ は $c_i$ 個です $(1\le i\le 9)$．これら $N$ 個の整数を並べ替え，それを $N$ 桁の $10$ 進法の整数 $M$ とみなしたとき，$M$ として考えられるものの 総和 を求めてください．

ただし，答えは非常に大きくなる可能性があるので ${10}^9+7$ で割った余りを出力してください．

入力

$N$
$c_1{c}_2{c}_3{c}_4{c}_5{c}_6{c}_7{c}_8{c}_9$

• $1\le N\le 2\times {10}^5$
• $c_i\ge 0$
• ${\displaystyle \sum _{i=1}^9{c}_i=N}$
• 入力は全て整数である

サンプル

3
1 1 1 0 0 0 0 0 0

1332

3
1 2 0 0 0 0 0 0 0

555

1
0 1 0 0 0 0 0 0 0

2

9
1 1 1 1 1 1 1 1 1

998387207