Chủ tịch K từng có một xâu \(S\) độ dài \(N\) gồm các chữ cái tiếng Anh viết thường, nhưng ông đã quên mất xâu đó. Ông có một cuốn từ điển ghi nhiều kiểu lỗi chính tả và từng tra cứu các lỗi chính tả của \(S\). Vì vậy, ông còn nhớ thông tin sau:

• Gọi \(T_i\) (\(1\le i\le N\)) là xâu thu được khi xóa ký tự thứ \(i\) của \(S\) rồi dồn các ký tự còn lại để lấp chỗ trống. Với mỗi \(1\le j\le M\), ta có \(T_{A_j}\le T_{B_j}\).

Ở đây, \(T_{A_j}\le T_{B_j}\) nghĩa là hai xâu bằng nhau, hoặc \(T_{A_j}\) nhỏ hơn \(T_{B_j}\) theo thứ tự từ điển (thứ tự bảng chữ cái).

Cho những thông tin mà chủ tịch K nhớ, hãy tính số xâu \(S\) không mâu thuẫn với chúng, lấy phần dư khi chia cho \(1\,000\,000\,007\).

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả giá trị đều là số nguyên.

N M
A_1 B_1
A_2 B_2
...
A_M B_M

Dữ liệu ra

In một dòng chứa số xâu \(S\) không mâu thuẫn với thông tin đã cho, lấy phần dư khi chia cho \(1\,000\,000\,007\).

Ràng buộc

• \(2\le N\le 500\,000\).
• \(1\le M\le 500\,000\).
• \(1\le A_j,B_j\le N\) và \(A_j\ne B_j\) (\(1\le j\le M\)).
• \((A_j,B_j)\ne(A_k,B_k)\) với mọi \(1\le j<k\le M\).

Phân nhóm

• Nhóm 1 (8 điểm): \(N\le 10\).
• Nhóm 2 (20 điểm): \(N\le 200\).
• Nhóm 3 (29 điểm): \(M=N-1\). Ngoài ra, tồn tại một hoán vị \(P\) của \((1,2,\ldots,N)\) sao cho \(A_j=P_j\) và \(B_j=P_{j+1}\) với mọi \(1\le j\le M\).
• Nhóm 4 (32 điểm): \(N\le 20\,000\).
• Nhóm 5 (11 điểm): Không có ràng buộc bổ sung.

Ví dụ

3 2
1 3
3 2

5876

5 6
1 2
1 5
2 4
5 4
5 3
4 3

656981

10 9
3 6
4 6
6 7
7 9
10 8
9 8
8 5
5 2
5 1

206289833

7 6
1 3
3 4
4 6
6 5
5 7
7 2

7125651

5 4
2 4
4 3
3 5
5 1

61451

Nguồn

Bài toán thuộc JOI 2021/2022, trại huấn luyện mùa xuân, ngày thi 1 (20/03/2022). Bản gốc do JCIOI phát hành theo giấy phép CC BY-SA 4.0. Bản tiếng Việt là bản dịch từ đề chính thức.