This problem boils down to counting the number $ N $ of contiguous subsets whose sum of elements is equal to $ 2 $ module $ 4 $.

Let the input matrix be $ A = langle a_1, dots, a_n rangle $ and let $ B = langle b_0, dots, b_n rangle $ be a set of $ n + 1 $ elements where $ b_i = sum_ {j = 1} ^ i a_i $. It should be easy to see what you can build $ B $ in linear time.

by $ k = $ 0.1.2.3, leave $ eta_k $ be the number of elements in $ B $ which are equal to $ k $ module 4.

A contiguous subset $ langle a_ {i + 1}, dots, a_j rangle $ of $ A $ has sum 2 module 4 if and only if $ b_j – b_i = 2 pmod {4} $ so we can count the number of ways to select two different indices $ i, j in {0, dots, n } $ such that $ b_j – b_ {i} = 2 pmod {4} $ .

This only happens if $ {b_i, b_j } $ is one of $ {0, 2 } $or $ {1, 3 } $.

exist $ eta_0 cdot eta_2 $ sets of $ {b_i, b_j } $ the first type, and $ eta_1 cdot eta_3 $ sets of the second type.

Thus:

$$

N = eta_0 cdot eta_2 + eta_1 cdot eta_3.

$$