Count XOR Subarrays

Given an array A of n integers and an integer k, your task is to count the number of subarrays whose cumulative XOR is exactly equal to k. A subarray is defined as a contiguous segment of the array.

The cumulative XOR for a subarray A[l...r] is defined as:

\( \text{XOR}(A[l], A[l+1], \dots, A[r]) = A[l] \oplus A[l+1] \oplus \dots \oplus A[r] \)

Efficient solutions use the idea of prefix XOR and hashmaps to count the frequency of previous XOR values to determine the number of qualifying subarrays in O(n) time.

inputFormat

The first line contains two integers n and k separated by a space, where n is the number of elements in the array and k is the target XOR value.

The second line contains n integers separated by spaces representing the array A.

Input Format (stdin):

 
A[0] A[1] ... A[n-1]

outputFormat

Output a single integer which is the number of subarrays of A whose cumulative XOR equals k.

Output Format (stdout):

## sample

1 4
4

1