XOR-шляхи
XOR-шляхи
Дано прямокутне поле розміру n × m. У кожній клітині записано ціле число; число, записане в клітці (i, j) дорівнює a[i, j]. Ваше завдання - порахувати кількість шляхів з клітки (1,1) в клітину (n, m), які задовольняють таким умовам:
• З клітини можна переміщатися тільки вниз або тільки вправо. Більш формально, з клітки (i, j) можна переміститися в клітку (i, j + 1) або в клітку (i + 1, j). Клітка, в яку здійснюється переміщення, не може перебувати за межами поля.
• Xor всіх чисел на шляху з клітки (1,1) в клітину (n, m) має дорівнювати k.
Знайдіть кількість відповідних шляхів для заданого поля.
Вхідні дані
Перший рядок вхідних даних містить три цілих числа n, m і k( 1 ≤ n, m ≤ 20, 0 ≤ k ≤ 1018
) - висота і ширина поля, і число k.
Наступні n рядків містять по m цілих чисел кожна, де j-й елемент i-го рядка дорівнює
ai
, j(0 ≤ a[i, j] ≤ 1018
).
Вихідні дані
Виведіть одне ціле число - кількість шляхів з (1,1) в (n, m) з xor всіх чисел на шляху рівним k.
3 3 11 2 1 5 7 10 0 12 6 4
3
3 4 2 1 3 3 3 0 3 3 2 3 0 1 1
5