Count Binary Sequence

2 secs 1024 MB
seekworser

注釈


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

問題文


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

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

制約


入力


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

出力


答えを1行で出力せよ。

サンプル


入力1
3 2
1 2
2 3
出力2
2

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

入力2
4 2
1 3
2 4
出力2
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]
入力3
2 0
出力3
4

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

入力4
50 6
46 48
3 41
13 45
4 21
10 29
2 5
出力4
59926715

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

提出


Go (1.14)