Farmer John không hề hay biết rằng Bessie là một người rất yêu nghệ thuật! Gần đây nhất, cô bắt đầu nghiên cứu tác phẩm của nhiều nhà thơ vĩ đại, và giờ cô muốn thử tự sáng tác thơ.

Bessie biết \(N\) từ (\(1 \leq N \leq 5000\)) và muốn sắp xếp chúng thành những bài thơ. Bessie đã xác định độ dài tính theo số âm tiết của mỗi từ, đồng thời phân chúng vào các "lớp vần". Mỗi từ chỉ vần với những từ khác thuộc cùng lớp vần.

Mỗi bài thơ của Bessie gồm \(M\) dòng (\(1 \leq M \leq 10^5\)), và mỗi dòng phải có \(K\) âm tiết (\(1 \leq K \leq 5000\)). Hơn nữa, thơ của Bessie phải tuân theo một sơ đồ gieo vần cụ thể.

Bessie muốn biết cô có thể viết bao nhiêu bài thơ khác nhau thỏa mãn các ràng buộc đã cho.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(M\) và \(K\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số \(s_i\) (\(1 \leq s_i \leq K\)) và \(c_i\) (\(1 \leq c_i \leq N\)). Điều này cho biết Bessie biết một từ có độ dài \(s_i\) âm tiết và thuộc lớp vần \(c_i\).

\(M\) dòng cuối cùng mô tả sơ đồ gieo vần mà Bessie mong muốn, mỗi dòng chứa một chữ cái in hoa \(e_i\). Tất cả các dòng ứng với cùng một giá trị \(e_i\) phải kết thúc bằng những từ thuộc cùng một lớp vần. Các dòng có giá trị \(e_i\) khác nhau không nhất thiết phải kết thúc bằng những từ thuộc các lớp vần khác nhau.

Dữ liệu ra

In ra số bài thơ Bessie có thể viết thỏa mãn các ràng buộc này. Vì số này có thể rất lớn, hãy tính kết quả theo modulo \(1\,000\,000\,007\).

Ví dụ

3 3 10
3 1
4 1
3 2
A
B
A

960

Nguồn

Đề bài gốc: USACO 2019 January Contest, Gold — Cow Poetry

Tác giả: Jay Leeds