問題文

Penguinman は市場を運営しています。

この市場では、この時点で以下の $4$ つのことが決まっています。

• $N$ 人の客が来ること。
• $M$ 個の品物を売ること。それぞれの品物には値段と価値が定まっており、$i$ 個目の品物の値段は $A_i$ 円,価値は $B_i$ である。ただし、 $i≠j$ ならば $B_i≠B_j$ であることが保証される。
• 全ての客は $0$ 円以上 $K$ 円以下のうち好きな金額（整数）を等しい確率で持ってくること。
• 客は持ってきたお金で買えるもののうち最も価値の高いものを $1$ つだけ買うこと。買われた品物はその時点で市場からなくなる。買えるものがない時は買い物を諦めて帰ることとし、またこの問題の制約のもと買う品物は一意に定まる。

Penguinman の部下であるあなたの仕事は、客が買う品物の価値の総和の期待値を求めることです。

この期待値は $2$ つの正の整数 $P,Q$ を用いて $P/Q$ で表すことができることが保証されるので、 $R×Q≡P(\bmod 10^9+7)$ となるような $0$ 以上 $10^9+6$ 以下の整数 $R$ を求め、出力してください。

入力

$N\ M\ K$
$A_1\ B_1$
$A_2\ B_2$
$︙$
$A_M\ B_M$

• $1≤N,M≤40$
• $1≤K≤10^9$
• $1≤A_i≤K$
• $1≤B_i≤10^9$
• $i≠j$ ならば $B_i≠B_j$
• 入力は全て整数

出力

最後に改行してください。

サンプル

2 1 2
1 1

888888896

10 3 100
2 4
5 100
1 101

974312872

40 6 1000000
400 100
20 1
1030 11
593 103
194029 103948
20 9183

621015348