Here is the problem link -

https://www.codechef.com/CODG2021/problems/CODIGO04

In the ANNOUNCEMENTS section they specified the correct output for testcase

5 3

abcde

is 13 not 12 , which was true (we can verify by checking all valid splitings ) , **but the accepted solutions** ( first two at the top in Successful Submissions ) **are giving 12** as **output but still was accepted.**

My solution link -

https://www.codechef.com/viewsolution/41940139

And the idea was to store the number of valid solutions for size upto i-1 to calculate the valid solutions for size i by the following logic

The possible splitings with size i=valid solutions of size i-1( where last element was not included in previous adjacent subarray) +no valid solutions when we add the last element to previous sub array( = valid solutions of size i-1 - no solutions where last sub array was size k , which was dp[i-k-1] )

**Is there anything wrong with my logic / implementation / question / Tester ??**

My code -

```
#include <iostream>
#include<vector>
#include<string>
using namespace std;
int main() {
int t;
cin >> t;
while(t--){
int n,k;
cin >> n >> k;
string s;
cin >> s;
vector<int> dp(n);
int mod = 1000000007;
dp[0] = 1;
for(int i=1;i<n;++i){
long long int minus{};
if(i-k > 0) minus = dp[i-k-1];
else if(i-k == 0) minus = 1;
long long int ev = ((long long int)dp[i-1] * 2 - minus);
if(ev < 0) ev+=mod;
ev %= mod;
dp[i] = ev;
}
cout << dp[n-1] << "\n";
}
return 0;
}
```