Xét các đồ thị vô hướng đơn, liên thông, có các đỉnh \(0,1,\ldots,n-1\). Hàm DFS(d,v) in d/v, đánh dấu \(v\), rồi duyệt các đỉnh kề của \(v\) theo thứ tự tăng dần; với mỗi đỉnh chưa thăm \(w\), nó gọi DFS(d+1,w).

Bạn nhận được toàn bộ kết quả in của lời gọi DFS(0,n-1) trên một đồ thị chưa biết. Hãy đếm số đồ thị khác nhau có thể tạo ra đúng kết quả đó.

Dữ liệu vào

Gồm \(n\) dòng là kết quả của DFS, mỗi dòng có dạng d/v. Dòng đầu luôn là 0/n-1.

Dữ liệu ra

In số đồ thị thỏa mãn, lấy modulo \(1\,000\,000\,007\).

Ràng buộc

• \(1\le n\le2\cdot10^5\).

Phân nhóm

1. \(10\) điểm: \(n\le6\).
2. \(20\) điểm: \(n\le500\).
3. \(20\) điểm: \(n\le10^4\).
4. \(10\) điểm: với mọi \(i=2,\ldots,n\), dòng \(i\) là i-1/i-2.
5. \(20\) điểm: với mọi \(i=2,\ldots,n\), dòng \(i\) là i-1/v với \(v\in\{0,\ldots,n-2\}\).
6. \(20\) điểm: không có ràng buộc thêm.

Ví dụ

0/2
1/0
2/1

2

Nguồn

CEOI 2026 - Ngày 1, bài DFS.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn CEOI 2026 chính thức.