Mô tả và yêu cầu

Mặc dù Farmer John không hề hay biết, nhưng Bessie lại là một người rất yêu nghệ
thuật! Gần đây, cô đã nghiên cứu nhiều tác phẩm thơ nổi tiếng và giờ đây muốn thử sức
sáng tác thơ của riêng mình.
Bessie có N từ (1 ≤ N ≤ 5000), và cô muốn dùng những từ này để viết thành các bài
thơ. Cô đã xác định độ dài của từng từ (tính theo số âm tiết), đồng thời chia các từ vào các
nhóm gieo vần. Mỗi từ chỉ có thể gieo vần với các từ thuộc cùng một nhóm vần.
Mỗi bài thơ của Bessie sẽ gồm M dòng (1 ≤ M ≤ 10⁵), và mỗi dòng phải có đúng K
âm tiết (1 ≤ K ≤ 5000). Hơn nữa, bài thơ phải tuân thủ theo một mẫu gieo vần cụ thể.
Nhiệm vụ của bạn là giúp Bessie xác định có bao nhiêu cách khác nhau để viết một bài thơ
thoả mãn tất cả những yêu cầu trên.

Dữ liệu vào

 Dòng đầu tiên chứa ba số nguyên N, M, K.

 N dòng tiếp theo, mỗi dòng gồm hai số nguyên 𝑠𝑖 (1 ≤ 𝑠𝑖 ≤ 𝐾) và 𝑐𝑖 (1 ≤ 𝑐𝑖 ≤
𝑁). Điều này có nghĩa là Bessie biết một từ dài 𝑠𝑖 âm tiết và thuộc nhóm gieo vần
𝑐𝑖.

 M dòng cuối mô tả mẫu gieo vần của bài thơ. Mỗi dòng chứa một ký tự in hoa 𝑒𝑖,
đại diện cho ký hiệu gieo vần của dòng đó. Các dòng có cùng ký hiệu 𝑒𝑖 phải kết
thúc bằng từ thuộc cùng một nhóm vần. Các dòng có ký hiệu khác nhau có thể kết
thúc bằng từ thuộc các nhóm vần khác nhau.

Dữ liệu ra

Ghi ra số lượng bài thơ khác nhau mà Bessie có thể viết thoả mãn các điều kiện đã
cho. Do kết quả có thể rất lớn, hãy in ra kết quả modulo 1,000,000,007.

Ví dụ

INPUT                                           OUTPUT
       3 3 10                                             960

       3 1

       4 1

       3 2

       A

       B

       A

Giải thích:
        Trong ví dụ này, Bessie có 3 từ. Hai từ đầu thuộc cùng nhóm vần và có độ dài lần
lượt là 3 và 4 âm tiết. Từ cuối cùng có 3 âm tiết và thuộc nhóm vần khác.
Cô cần viết một bài thơ gồm 3 dòng, mỗi dòng gồm 10 âm tiết. Đồng thời, dòng đầu và
dòng cuối phải vần với nhau (ký hiệu ‘A’), còn dòng giữa có thể kết thúc bằng một từ
thuộc nhóm vần khác (‘B’).
Có tổng cộng 960 cách để viết bài thơ thoả mãn điều kiện trên. Một ví dụ là trình tự từ:
121 123 321, trong đó 1, 2, 3 lần lượt là chỉ số của các từ trong danh sách ban đầu.