No.147 試験監督(2)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 128 MB / 通常問題
タグ : / 解いたユーザー数 68
作問者 : LayCurseLayCurse
7 ProblemId : 370 / 出題時の順位表

問題文

とある教員(匿名希望)は,すぐ近くでは節分祭をやっている中,期末試験の試験監督をしている時に以下の問題を考えました.

カンニング防止の為,受講生は同じ机で隣同士の席に座ることはできません.
例えば,$3$ つの椅子がある机の場合,$2$ 人の受講生が座る場合は両端の椅子を使う以外は許されておらず,$1$ 人の受講生が座る場合は $3$ つのうちどの椅子でも使うことができます.
ある部屋では,$N$ 種類の机があり,$C_k$ 個の椅子がある机が $D_k$ 個あります.
ここで,$C_k$ 個の椅子がある机は,$C_k$ 個の椅子が直線上に配置されています.
何人の人が試験を受けるかわかりませんが,使われる椅子の配置として,ありうる配置のパターン数を ${\rm mod}\ 10^9+7$ で求めるプログラムを書いてください.


図1.試験日(2/3)の翌日も節分祭らしいが…(吉田神社前,2015年2月4日)

入力

$N$
$C_1$ $D_1$
$C_2$ $D_2$
$\vdots$
$C_N$ $D_N$

$1 \leq N \leq 30000 = 3 \times 10^4$
$1 \leq C_k \leq 10^{18}$
$1 \leq D_k \leq 10^{200}$
$i \neq j$ のとき $C_i \neq C_j$

出力

使われる椅子のパターン数を ${\rm mod}\ 10^9+7$ で出力して下さい.

サンプル

サンプル1
入力
1
3 1
出力
5

問題文にある通り,3つの椅子がある机の場合は,誰も座らない場合が1通り,誰か1人がどこかの椅子に座る場合が3通り,2人が両端に座る場合が1通りで,合計5通りです.
椅子の使われ方が問題なので,2人の受講生は区別しないことに注意して下さい.

サンプル2
入力
2
1 2
3 1
出力
20

それぞれの1つの椅子がある机が使われるかどうかで,パターンの数が4倍になるそうです.

サンプル3
入力
3
10 10
20 20
30 30
出力
500979274
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。