Thơ bò

• $N$ từ (âm tiết $s_i$, vần $c_i$), viết bài thơ $M$ dòng (mỗi dòng $K$ âm tiết). Mỗi dòng có chữ cuối, vần phải khớp theo pattern. Đếm số bài thơ khác nhau, mod ${10}^9+7$.

  Dữ liệu vào

• $N$ $M$ $K$. $N$ dòng: $s_i$ $c_i$. Dòng cuối: $M$ chữ cái (pattern).

  Dữ liệu ra

Số bài thơ mod ${10}^9+7$.

Ví dụ