# Count total subsequences whose sum is divisible by k

I am trying to write a DP solution for the problem: count total number of sub-sequences possible of an array whose elements’ sum is divisible by k.

I have written the following solution. But it is not giving the correct result. Like in the following code snippet, the array is {1, 2, 1} and k = 3. So expected total number of sub sequences divisible by 3 is 2, but the actual result is 3 which is clearly incorrect.

Please point out my mistake.

```private int countDP(int[] a, int k)
{
int L = a.length;

int[][] DP = new int[L][k];

for(int i = 0; i < DP.length; i++)
{
for(int j = 0; j < DP.length; j++)
DP[i][j] = -1;
}

int res = _countDP(a, k, DP, 0, 0);

return res;
}

private int _countDP(int[] a, int k, int[][] DP, int idx, int m) //Not giving the correct result.
{
if(idx == a.length)
return m == 0 ? 1 : 0;

if(DP[idx][m] != -1)
return DP[idx][m];

int ans = 0;

ans = _countDP(a, k, DP, idx + 1, m);
ans += _countDP(a, k, DP, idx + 1, (m + a[idx]) % k);

return DP[idx][m] = ans;
}

public static void main(String[] args)
{
CountSubnsequences cs = new CountSubnsequences();

int[] a = {1, 2, 1};
int k = 3;

int total1 = cs.countDP(a, k);

System.out.println("Total numeber of sub sequences: " + total1);
}
```

Let `s` denote a sequence of length `N`, and `K` be a given divisor.

`dp[i][j]` = the number of subsequences of `s[0..i]` with remainder equal to `j`. We will compute `dp` for all `0 <= i < N` and `0 <= j < K`.

```dp[i][j] = 0 for all  (i, j)

dp += 1
dp[s mod K] += 1

for i = 1 .. N - 1
for j = 0 .. K - 1
dp[i][j] = dp[i - 1][j]
for j = 0 .. K - 1
dp[i][(j + s[i]) mod K] += dp[i - 1][j]
```

The result is `dp[N - 1]`