The Non-Divisible Path

Given an N x M grid of positive integers and a divisor K, find the number of unique paths from the top-left cell (0,0) to the bottom-right cell (N-1, M-1). You can only move Right or Down. A path is valid if the cumulative sum of the numbers encountered so far is NEVER divisible by K at any step along the path, EXCEPT possibly at the very first cell (0,0). Input: First line: N M K Next N lines: M integers each representing the grid. Output: Number of valid paths. Example: Input: 2 2 3 1 1 1 1 Output: 0 Explanation: Any path to (1,1) has a cumulative sum of 1 -> 2 -> 3. Since 3 is divisible by 3, no paths are valid.