Odd subsequences

You are given an array $A$ consisting of $N$ elements. Find the number of subsequences of length $K$ with odd sum modulo ${10}^9+7$.

Example:

Input:  n=5, k=2, a[] = { 1, 2, 3, 4, 5 }
Output: 6

Approach

Java

import java.io.IOException;

public class OddSubsequences {
    final public static long mod = (long) 1e9 + 7;

    public static void main(String[] args) throws IOException {
        int n = 5, k = 2;
        int[] a = { 1, 2, 3, 4, 5 };
        long dp[][] = new long[k + 1][2];
        dp[0][0] = 1;
        dp[0][1] = 0;
        for (int i = 0; i < n; ++i) {
            if ((a[i] & 1) != 0) {
                for (int l = k; l > 0; --l) {
                    for (int j = 0; j < 2; ++j) {
                        dp[l][j] = (dp[l][j] + dp[l - 1][j ^ 1]) % mod;
                    }
                }
            } else {
                for (int l = k; l > 0; --l) {
                    for (int j = 0; j < 2; ++j) {
                        dp[l][j] = (dp[l][j] + dp[l - 1][j]) % mod;
                    }
                }
            }
        }
        System.out.println(dp[k][1]);
    }
}