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≤m≤5;1≤n≤10^5). Vòng số thứ i sẽ chứa n số nguyên a(i,1);a(i,2);…;a(i,n) (|a(i,j)|≤10^9;1≤i≤m;1≤j≤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|≤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.

Dữ liệu:

Vào từ tệp CAU4.INP: 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ả:

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

Ví dụ 1:

CAU4.INP

2 3 5
1 2 1
3 4 4

CAU4.OUT

5

Ví dụ 2:

CAU4.INP

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

CAU4.OUT

2

Ràng buộc:

- Có 30% số test ứng với 30% số điểm của bài có m=2,n≤10^5;
- Có 40% số test ứng với 40% số điểm của bài có m=4,n≤10^3;
- Có 30% số test ứng với 30% số điểm của bài có m=5,n≤400.