Chúng ta có thể tạo ra một ô chữ vô tận 8-hướng bằng cách lặp lại một khối chữ kích thước ~M \times N~ vô số lần. Giả sử chúng ta có khối chữ sau:
honi
hsin
Với khối chữ trên, ta tạo ra ô chữ vô tận 8-hướng sau:
...honihonihonihoni...
...hsinhsinhsinhsin...
...honihonihonihoni...
...hsinhsinhsinhsin...
Với ô chữ đã tạo, ta sẽ chọn ngẫu nhiên một ô và một hướng bất kì trong 8 hướng. Sau đó, ta sẽ viết xuống một từ gồm ~K~ chữ cái bắt đầu từ ô được chọn và đi theo hướng được chọn. Nếu ta thực hiện thao tác trên hai lần một cách độc lập, ta sẽ thu được hai từ với độ dài ~K~. Hãy tính xác suất thu được hai từ giống nhau.
Input
Dòng đầu tiên chứa các số nguyên ~M~, ~N~, ~K~ ~(1 \leq M,N \leq 500, \: 2 \leq K \leq 10^9)~.
Mỗi dòng trong số ~M~ dòng tiếp theo chứa ~N~ chữ cái Tiếng Anh in thường, mô tả một khối chữ trong ô chữ. Khối chữ được đảm bảo sẽ có ít nhất hai chữ cái phân biệt.
Output
In ra xác suất cần tìm dưới dạng một phân số tối giản ~p/q~ (không chứa khoảng trắng).
Subtask
- ~5~ test đầu tiên có ~M=N~.
- ~3~ test còn lại không có ràng buộc gì thêm.
Sample 1
Input
1 2 2
ab
Output
5/16
Sample 2
Input
2 4 3
honi
hsin
Output
19/152
Sample 3
Input
3 3 10
ban
ana
nab
Output
2/27
Comments