Cho một ma trận kích thước \(m \times n\), hãy đếm số ma trận con mà có tổng chia hết cho một số \(k\) cho trước.

Dữ liệu:

• Dòng đầu chứa số nguyên \(m,n,k\);
• M dòng tiếp theo, mỗi dòng chứa n số nguyên \(a_{i,1},a_{i,2},...,a_{i,n} (a_{i,j} \le 10^9)\)

Kết quả: một số nguyên duy nhất là số ma trận con mà có tổng chia hết cho \(k\)

Ràng buộc:

• 30% số test ứng với 30% số điểm có \(m,n \le 10\)
• 40% số test ứng với 40% số điểm có \(m,n \le 100\)
• 30% số test ứng với 30% số điểm có \(m,n \le 500\)

Input

2 3 9
3 3 3
1 2 6

Output

5

Giải thích

Có 5 ma trận có mà có tổng chia hết cho 9