Cho $n$ ô hàng ngang được đánh số từ 1 đến $n$. Cho $k$ đoạn số nguyên, đoạn thứ $i$ có dạng $[l_i, r_i]$, không có hai đoạn nào giao nhau. Đang ở vị trí ô thứ $c$, bạn có thể thực hiện thao tác di chuyển như sau:

• Chọn một số nguyên $x$ sao cho tồn tại một chỉ số $i$ thỏa mãn $l_i \le x \le r_i$, di chuyển đến ô $c + x$.
  Bạn hãy đếm số cách di chuyển từ ô thứ 1 đến ô thứ $n$.

Hai đoạn $[a, b]$ và $[c, d]$ được gọi là giao nhau khi và chỉ khi tồn tại một số nguyên $z$ thỏa mãn $a \le z \le b$ và $c \le z \le d$.

Input:

• Dòng đầu tiên chứa hai số nguyên $n$ và $k$ $(2 \leq n \leq 2 \times 10^5 ; 1 \leq k \leq \min(n,10))$.
• $k$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $l_i$ và $r_i$ mô tả đoạn $[l_i, r_i]$ $(1 \leq l_i \leq r_i \leq n)$.
• Dữ liệu đảm bảo không có hai đoạn nào giao nhau.

Output:

• In ra số cách di chuyển từ từ ô thứ 1 đến ô thứ $n$, kết quả chia lấy dư cho $818976480$.

6 2
3 4
1 1

6

3 1
2 2

1