Wednesday và các bạn bị nhốt vào một căn phòng với rất nhiều cạm bẫy. Tuy nhiên, là một người thông minh và dũng cảm, Wednesday đã giúp cả nhóm vượt qua được hầu như tất cả khó khăn để đến cửa ra của căn phòng. Ở cửa ra có một chiếc ổ khóa với kết cấu rất kì dị.

Trên chiếc ổ khóa có ~m~ vòng khóa, mỗi vòng ghi ~n~ số nguyên (~2 \le m \le 5~, ~1 \le n \le 10^5~). Vòng số thứ ~i~ chứa ~n~ số nguyên ~a_{i,1}, a_{i,2}, \dots, a_{i,n}~ (~|a_{i,j}| \le 10^9~, ~1 \le i \le m~, ~1 \le j \le n~). Các vòng số có thể xoay tròn. Mỗi bước xoay, trên mỗi vòng số chỉ hiện đúng một số. Để mở được ổ khóa, Wednesday cần phải xoay các vòng số sao cho tổng ~m~ số hiện trên ~m~ vòng số này đúng bằng ~S~ (~|S| \le 10^9~).

Yêu cầu: Cho các giá trị trên ~m~ vòng số, hãy giúp Wednesday đếm xem có bao nhiêu cách xoay để mở được ổ khóa này. Hai cách xoay được coi là khác nhau nếu có ít nhất một vòng hiện số ở vị trí (chỉ số ~j~) khác nhau, kể cả khi giá trị bằng nhau.

Dữ liệu

• Dòng đầu tiên ghi ba số nguyên ~m, n, S~ như mô tả ở đề bài.
• ~m~ dòng tiếp theo, mỗi dòng ghi ~n~ số nguyên cho biết các giá trị trên từng vòng số.

Kết quả

In ra một số nguyên duy nhất là số cách để mở được ổ khóa đặc biệt này.

Ví dụ

Ví dụ 1

BAI4.INP

2 3 5
1 2 1
3 4 4

BAI4.OUT

5

Ví dụ 2

BAI4.INP

4 10 6
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9

BAI4.OUT

84

Ví dụ 3

BAI4.INP

5 2 2
1 2
1 2
1 2
1 2
-2 -2

BAI4.OUT

2

Giới hạn

• Subtask 1 (30% số điểm): ~m = 2~, ~n \le 10^5~.
• Subtask 2 (40% số điểm): ~m = 4~, ~n \le 10^3~.
• Subtask 3 (30% số điểm): ~m = 5~, ~n \le 400~.