AT_joigsp2025_j 電波塔 (Radio Towers)

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 $ で割ったあまりを求めるプログラムを作成せよ． ---

入力は以下の形式で標準入力から与えられる． > $ N $ $ L $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ B_N $

標準出力に，条件を満たす塔の選び方の個数を $ 1\,000\,000\,007 $ で割ったあまりを $ 1 $ 行で出力せよ．

### 小課題 1. ( $ 20 $ 点) $ N \leqq 16 $ ． 2. ( $ 20 $ 点) $ N \leqq 5\,000 $ ． 3. ( $ 25 $ 点) $ L = 0 $ ． 4. ( $ 35 $ 点) 追加の制約はない． --- ### Sample Explanation 1 電波塔 $ 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 $ を出力する． この入力例はすべての小課題の制約を満たす． --- ### Sample Explanation 2 この入力例は小課題 $ 1,2,4 $ の制約を満たす． --- ### Sample Explanation 3 この入力例は小課題 $ 1,2,4 $ の制約を満たす． ### Constraints - $ 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 $ )． - 入力される値はすべて整数である．