Thơ bò

Bessie đang tập làm thơ. Cô bò có một cuốn từ điển gồm $N$ từ; từ thứ $i$ có $s_i$ âm tiết và thuộc lớp vần $c_i$. Hai từ vần với nhau khi và chỉ khi chúng thuộc cùng một lớp vần.

Một bài thơ gồm $M$ dòng, mỗi dòng có đúng $K$ âm tiết. Một dòng là một dãy từ có thứ tự (mỗi từ được dùng bao nhiêu lần tuỳ ý) sao cho tổng số âm tiết của các từ trong dãy đúng bằng $K$. Vần của một dòng là lớp vần của từ cuối cùng trên dòng đó.

Bessie đã chọn sẵn sơ đồ gieo vần: dòng thứ $j$ được gán một chữ cái in hoa. Hai dòng mang cùng một chữ cái bắt buộc phải cùng vần. Hai dòng mang chữ cái khác nhau thì không bị ràng buộc gì, chúng có thể cùng vần hoặc không.

Hai bài thơ được coi là khác nhau nếu tồn tại một vị trí mà từ đứng ở đó khác nhau. Hãy đếm số bài thơ hợp lệ, lấy phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $N$, $M$, $K$.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $s_i$ và $c_i$.
• $M$ dòng cuối, mỗi dòng chứa một chữ cái in hoa mô tả sơ đồ gieo vần.

Dữ liệu ra

Một số nguyên duy nhất: số bài thơ hợp lệ theo modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le 5000$
• $1\le M\le {10}^5$
• $1\le K\le 5000$
• $1\le s_i\le K$
• $1\le c_i\le N$
• Mỗi chữ cái trong sơ đồ gieo vần nằm trong khoảng từ A đến Z.

Ví dụ