Khóa số

Wednesday và các bạn bị nhốt trong một căn phòng với một chiếc khóa số có \(m\) vòng xoay.
Mỗi vòng có đúng \(n\) số được ghi theo thứ tự vòng tròn. Ở mỗi thời điểm, mỗi vòng chỉ hiển thị một số.

Cụ thể, vòng thứ \(i\) có dãy \(a_{i,1}, a_{i,2}, \ldots, a_{i,n}\) (các vòng có thể xoay độc lập).
Sau khi xoay, ở vòng \(i\) sẽ hiển thị một trong \(n\) số của vòng đó.

Để mở khóa, tổng \(m\) số đang hiển thị phải bằng đúng \(S\).

Hãy đếm số cách xoay (tức là số cách chọn mỗi vòng một vị trí hiển thị) sao cho tổng bằng \(S\).

Input

• Dòng đầu chứa ba số nguyên \(m, n, S\).
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa \(n\) số nguyên \(a_{i,1}, a_{i,2}, \ldots, a_{i,n}\).

Output

In ra một số nguyên duy nhất là số cách xoay để mở khóa.

Giới hạn

• \(2 \le m \le 5\)
• \(1 \le n \le 10^5\)
• \(|S| \le 10^9\)
• \(|a_{i,j}| \le 10^9\)

Scoring

• Subtask 1 (30%): \(m = 2\), \(n \le 10^5\).
• Subtask 2 (40%): \(m = 4\), \(n \le 10^3\).
• Subtask 3 (30%): \(m = 5\), \(n \le 400\).

Input

2 3 5
1 2 1
3 4 4

Output

5

Input

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

Output

84

Input

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

Output

2

Notes

Giải thích test ví dụ 1:

Ta có 5 cách chọn và các cặp giá trị xuất hiện trên vòng tương ứng là \((1,4),(1,4),(2,3),(1,4),(1,4)\).