Path Divisibility in a Matrix

You are given a matrix of non-negative integers with dimensions (n \times m) and an integer (k). Your task is to determine if there exists a path from the top-left corner (i.e. cell ((0, 0))) to the bottom-right corner (i.e. cell ((n-1, m-1))) such that the sum of all elements along the path is divisible by (k).

In this problem, you can only move either right or down from a cell. Formally, if you are at cell ((i,j)), you can move to ((i, j+1)) or ((i+1, j)) provided that these cells are within the boundaries of the matrix.

Find a valid path (if one exists) where the condition (\sum_{(i,j)\in path} matrix[i][j] \equiv 0 ; (\bmod; k)) holds. Output YES if such a path exists, and NO otherwise.

inputFormat

The first line contains three integers (n), (m), and (k) -- the numbers of rows, columns, and the divisor, respectively. This is followed by (n) lines, each containing (m) non-negative integers representing the matrix.

outputFormat

Output a single line with the string YES if there exists a path from the top-left to the bottom-right cell such that the sum of the elements along the path is divisible by (k); otherwise, output NO.## sample

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

YES