Splitting Sequence with Even Numbers

Given a sequence of integers, your task is to determine the number of ways to split the sequence into exactly k contiguous subarrays such that each subarray contains at least one even number.

Two ways of splitting are considered different if the positions of the splits differ.

For example, consider the sequence [1, 3, 2, 6, 4] with k = 2. Although the overall sum of the subarrays would be even in some cases, we are specifically interested in splits where every subarray has at least one even number. In this example, splitting the sequence after the third element (forming [1, 3, 2] and [6, 4]) or after the fourth element (forming [1, 3, 2, 6] and [4]) are valid, whereas splitting after the second element ([1, 3] and [2, 6, 4]) is not valid since the first subarray contains no even number. Thus, the answer is 2.

inputFormat

The first line contains two integers n and k, where n is the length of the sequence and k is the number of contiguous subarrays desired.

The second line contains n space-separated integers representing the sequence.

outputFormat

Output a single integer representing the number of ways to split the sequence into exactly k contiguous subarrays in which each subarray contains at least one even number.

5 2
1 3 2 6 4

2