Count Paths With the Given XOR Value

Challenge Points: 20

Level: Medium

You are given an m x n matrix grid, and an integer k. You need to count how many different paths exist from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1) with the following rules:

You may only move right or down at each step.
While moving along a path, take the XOR of all cell values in that path.
Only count the path if the final XOR result is exactly equal to k.

Since the answer may be large, return it modulo 1,000,000,007.

Example 1:

Input: grid = [[1,2],[3,4]], k = 4

Output: 0

Explanation:

Paths: 1 → 2 → 4 XOR = 1 ^ 2 ^ 4 = 7 (not valid) 1 → 3 → 4 XOR = 1 ^ 3 ^ 4 = 6 (not valid)

Example 2:

Input: grid = [[5]], k = 5

Output: 1

Explanation:

Only path is the single cell: 5 → XOR = 5

Example 3:

Input: grid = [[1,2,3],[4,1,7]], k = 6

Output: 0

Explanation:

One valid path: 1 → 2 → 3 → 7 (XOR = 1 ^ 2 ^ 3 ^ 7 = 6)

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result