Divisible Path in a Matrix

You are given a matrix of integers with n rows and m columns and an integer k. The task is to determine whether there exists a path from the top-left cell (1,1) to the bottom-right cell (n,m) moving only right or down such that the sum of all values along the path is divisible by k.

Formally, let path be a sequence of cells starting at (1,1) and ending at (n,m) where from cell (i,j) you can only move to (i+1,j) or (i,j+1). Let the sum along the path be S. You need to check if:

$$ S \equiv 0 \pmod{k} $$

Output "YES" if such a path exists, otherwise output "NO".

inputFormat

The input is given via standard input (stdin) with the following format:

1. The first line contains two integers n and m - the number of rows and columns.
2. The next n lines each contain m integers representing the matrix values.
3. The last line contains an integer k.

You are required to determine if there exists a path from the top-left corner to the bottom-right corner such that the sum of values along the path satisfies $$ S \equiv 0 \pmod{k} $$.

outputFormat

Output a single line via standard output (stdout): "YES" if such a path exists; otherwise, "NO".

3 3
1 3 1
1 5 1
4 2 2
4

YES