問題
$N$ 人の天使が左から順に $1$ 列に並んでいます。最初はすべての天使は掌握されていません。
また $M$ 個の操作の候補があります。 $i$ 個目の操作は以下を意味します。
- 左から $L_i$ 番目の天使から $R_i$ 番目までの天使を掌握する。 ここで, 区間内で既に掌握されている天使についても掌握状態のままである。
うくさんは操作の候補のうちのいくつかを選んで, それを行うことで $N$ 人全ての天使を掌握したいです。
このような操作の選び方の組み合わせを $10^9 + 7$ で割った余りで求めてください。
入力
$N$ $M$ $L_1$ $R_1$ $L_2$ $R_2$ $:$ $L_M$ $R_M$
$1$ 行目に天使の人数 $N(1 \le N \le 10^5)$ と操作の候補数 $M(1 \le M \le 2 \times 10^5)$ が与えられます。
つづく $M$ 行のうち $i$ 行目には $2$ つの整数 $L_i, R_i(1 \le L_i \le R_i \le N)$ が与えられます。 これは $i$ 個目の操作を行うことで左から $L_i$ 番目の天使から $R_i$ 番目までの天使を掌握することを意味します。
出力
$N$ 人全ての天使を掌握するような操作の選び方の組み合わせを $10^9 + 7$ で割った余りで求めてください。
最後に改行してください。
入出力例
入力例 1
3 3 1 3 1 2 2 3
出力例 1
5
$\{1\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}$ を選ぶ $5$ 通りの組み合わせが存在します。
入力例 2
10 4 1 4 6 10 1 3 6 7
出力例 2
0
どのように選んでも $5$ 番目の天使を掌握できません。