Count Binary Sequence

この問題は、以下の問題を題材に解きやすく改題したものです。
https://codeforces.com/contest/1767/problem/C

整数および個の制約が与えられます。
のみからなる長さの数列であって、以下の条件を満たすものの個数をで割った余りを出力してください。

条件
全てのについて、数列の番目から番目にはとの両方が含まれる。

N M
l0 r0
l1 r1
…
l(M-1) r(M-1)

答えを1行で出力せよ。

3 2
1 2
2 3

2

条件を満たす数列は[1, 0, 1]、[0, 1, 0]の2通りです。
[0, 0, 1]、[1, 1, 1]などは、いずれも条件を満たしません。

4 2
1 3
2 4

10

以下の10通りです。

• [0, 0, 1, 0]
• [0, 0, 1, 1]
• [0, 1, 0, 0]
• [0, 1, 0, 1]
• [0, 1, 1, 0]
• [1, 0, 0, 1]
• [1, 0, 1, 0]
• [1, 0, 1, 1]
• [1, 1, 0, 0]
• [1, 1, 0, 1]

2 0

4

条件が一つも与えられない場合もあります。

50 6
46 48
3 41
13 45
4 21
10 29
2 5

59926715

で割った余りを出力してください。