연발 사격

한 사격수가 사격 연습을 하고 있다. 1번부터 N번까지의 목표물이 일렬로 나열되어 있는데, 각 목표물에는 1 이상 1,000 이하의 자연수 형태로 점수가 기입되어 있다.

사격수는 명중률 100%를 자랑하여, 쏠 때마다 원하는 목표물을 정확히 맞힐 수 있다. 한 사격수는 연발 사격을 1회 하려고 한다. 이때, 연발 사격이란 연속된 위치에 속한 목표물들을 차례대로 맞히는 것을 의미한다. 단, N번 위치와 1번 위치는 연속적이지 않다.

또한, 사격수는 자신이 맞힐 연속된 목표물의 점수 합이 정확히 M이 되도록 만들 예정이다. 단, 가지고 있는 총알의 수는 K개이다. 또한 값이 짝수인 목표물만 맞히고자 한다.

사격수가 목표물의 위치 X부터 Y까지의 위치를 차례대로 맞힌다고 했을 때, 사격수의 목적을 만족하는 가능한 모든 (X, Y)의 조합의 수를 계산하는 프로그램을 작성하여라.

예를 들어 목표물의 수 N=12인 상황을 가정하자. 아래의 표는 각 위치의 목표물에 부여된 점수를 나타낸다. 이때, M=10, K=2라고 해보자.

이때, 가능한 모든 경우의 수는 구체적으로 (3, 4), (6, 7)로 두 가지만 존재하는 것을 확인할 수 있다. 다시 말해, 다음의 세 가지 조건을 만족하는 모든 경우의 수를 계산해야 한다.

(1) 연속된 목표물의 점수 합이 정확히 M이 되어야 한다. (2) 가지고 있는 총알의 수는 K개이다. (3) 맞히는 연속된 목표물의 점수 값은 모두 짝수여야 한다.

입출력 예시

예시 1

입력

12, 10, 2, [5, 5, 4, 6, 2, 2, 8, 5, 3, 2, 6, 2]

출력

2

예시 2

입력

15, 8, 3, [1, 2, 3, 4, 4, 5, 8, 8, 8, 2, 4, 4, 2, 1, 3]

출력

5

예시 3

입력

20, 10, 4, [2, 8, 3, 5, 2, 10, 1, 7, 4, 5, 4, 4, 2, 2, 4, 4, 4, 2, 10, 10]

출력

7

원본에서 모의고사 3회 2번입니다.