Cconvert

Tấm đang có $2$ xâu kí tự là $S$ và $T$ cùng với một bộ từ điển $N$ xâu kí tự có cùng độ dài $K$. Tấm muốn tìm cách sử dụng bộ từ điển này để biến đổi từ xâu $S$ sang xâu $T$ sao cho số lượng phép chuyển đổi là nhỏ nhất có thể.

Một xâu kí tự $X$ có thể chuyển đổi sang xâu kí tự $Y$ cùng độ dài nếu $2$ xâu chỉ khác nhau đúng một vị trí duy nhất. Ví dụ $X=\mathtt{\text{abcd}}$ và $Y=\mathtt{\text{abdc}}$ không thể chuyển đổi cho nhau vì chúng khác nhau ở kí tự thứ $3$ và $4$. $X=\mathtt{\text{abcd}}$ và $Y=\mathtt{\text{abce}}$ có thể chuyển đổi cho nhau vì chúng chỉ khác nhau ở kí tự thứ $4$.

Một cách biến đổi là một dãy $S=X_0\to X_1\to \dots \to X_x=T$, trong đó mỗi xâu trung gian $X_1,\dots ,X_{x-1}$ là một xâu trong từ điển và mỗi bước $X_{i-1}\to X_i$ là một phép chuyển đổi. Xâu $T$ không cần có trong từ điển. Nếu $S$ chuyển đổi được trực tiếp sang $T$ thì chỉ cần $1$ phép chuyển đổi. Hai cách biến đổi khác nhau nếu dãy xâu của chúng khác nhau.

Dữ liệu vào

• Dòng đầu tiên: chứa hai số nguyên $N,K$ $(1\le N\le 2000;1\le K\le 20)$.
• Dòng thứ hai: chứa xâu $S$ độ dài $K$.
• Dòng thứ ba: chứa xâu $T$ độ dài $K$.
• $N$ dòng tiếp theo: chứa $N$ xâu độ dài $K$ trong từ điển.

Tất cả các xâu ký tự chỉ chứa các ký tự latin từ 'a' đến 'z'. $S\ne T$, các xâu trong từ điển đôi một khác nhau và khác $S$, $T$.

Dữ liệu ra

Gồm $2$ số nguyên $x$ và $y$, trong đó $x$ là số lượng phép chuyển đổi ít nhất cần thực hiện, $y$ là số cách biến đổi khác nhau với $x$ phép chuyển đổi để chuyển đổi từ xâu $S$ sang xâu $T$. Vì số lượng cách chuyển đổi có thể rất lớn nên bạn chỉ cần in ra theo modulo ${10}^9+7$. Nếu không có đáp án ghi ra hai số $-1-1$.

Ràng buộc

• $1\le N\le 2000$
• $1\le K\le 20$
• $30\%$ số test: $N\le 10$.
• $30\%$ số test: $N\le 200$.
• $40\%$ số test: $N\le 2000$.

Ví dụ