EGOI 国では東西に N 本の電波塔が立ち並び，その間で情報の通信を行うことで，国民にインターネット通信を提供している． 電波塔には，西から順に 1 から N までの番号が付けられている． 電波塔 i (1 \leqq i \leqq N) は，西から波長が A_i 以上 A_i + L 以下の電波を受信することと，東へ波長 B_i の電波を送信することが可能である． つまり，1 \leqq i_1 < i_2 \leqq N について，A_{i_2} \leqq B_{i_1} \leqq A_{i_2} + L が成り立つとき，電波塔 i_1 から電波塔 i_2 に情報を伝達することができる．

最近の EGOI 国では，さらに安定したインターネット通信が求められている．EGOI 国政府は，「番号順に情報を伝達できるように電波塔を 1 本以上選ぶ方法の個数」を通信の安定性の基準とすることにした． 具体的には，以下の条件を満たす 1 本以上の塔の選び方の数を求めたい．

• 選んだ塔の番号を小さい方から順に i_1, i_2, \dots, i_k としたとき，すべての j (1\leqq j\leqq k-1) に対して A_{i_{j+1}} \leqq B_{i_j} \leqq A_{i_{j+1}} + L が成り立つ．

電波塔の送受信できる波長の情報が与えられたとき，条件を満たす塔の選び方の個数を 1\,000\,000\,007 で割ったあまりを求めるプログラムを作成せよ．

制約

• 2 \leqq N \leqq 300\,000．
• 0 \leqq L \leqq 300\,000．
• 1 \leqq A_i \leqq 300\,000 (1\leqq i \leqq N)．
• 1 \leqq B_i \leqq 300\,000 (1\leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (20 点) N \leqq 16．
2. (20 点) N \leqq 5\,000．
3. (25 点) L = 0．
4. (35 点) 追加の制約はない．

入力例 1

3 0
1 3
2 3
3 2

出力例 1

5

電波塔 1, 2, 3 を選んだ場合を考える．

• A_2 \leqq B_1 \leqq A_2 + L でないため，電波塔 1 から電波塔 2 に情報を伝達することはできない．
• A_3 \leqq B_2 \leqq A_3 + L であるため，電波塔 2 から電波塔 3 に情報を伝達することはできる．

よって，この選び方は条件を満たさない．

電波塔 1, 3 を選んだ場合を考える．

• A_3 \leqq B_1 \leqq A_3 + L であるため，電波塔 1 から電波塔 3 に情報を伝達することはできる．

よって，この選び方は条件を満たす．

条件を満たす塔の選び方は，\lbrace1\rbrace, \lbrace2\rbrace, \lbrace3\rbrace, \lbrace1, 3\rbrace, \lbrace2, 3\rbrace の 5 通りである． よって，5 を 1\,000\,000\,007 で割ったあまりである 5 を出力する．

この入力例はすべての小課題の制約を満たす．

入力例 2

8 2
1 3
5 1
6 7
7 5
5 2
2 1
3 1
1 6

出力例 2

36

この入力例は小課題 1,2,4 の制約を満たす．

入力例 3

10 3
1 5
2 3
2 4
5 4
10 7
7 9
4 3
3 7
7 7
6 5

出力例 3

109

この入力例は小課題 1,2,4 の制約を満たす．