問題文

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

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

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

入力

$N$
$C_1$ $D_1$
$C_2$ $D_2$
$⋮$
$C_N$ $D_N$

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

出力

使われる椅子のパターン数を $\mathrm{m}\mathrm{o}\mathrm{d}{10}^9+7$ で出力して下さい．

サンプル

1
3 1

5

2
1 2
3 1

20

3
10 10
20 20
30 30

500979274