How to convert a recursive solution to dynamic programming(3D-DP)

See more:

recursion

C++11

Yesterday I came across the following question in a contest:

Problem statement:
You are given an array ‘A’ of ‘N’ integers numbered from ‘0’ to ‘N - 1’ and a single integer ‘K’. You have to determine the count of subsequences where the length is greater than ‘1’, and the sum of consecutive elements is divisible by ‘K’.

A subsequence is an array that can be derived from the original array by deleting some of the elements without changing the order of the remaining elements.

Your task is to tell the number of subsequences having a length greater than ‘1’ and the sum of consecutive elements divisible by ‘K’. Since the answer may be very large, return it modulo ‘10^9 + 7’.

Constraints:
1 <= 'T' <= 10
1 <= 'N' <= 10^5
1 <= ‘K’ <= 10^9
1 <= ‘A[i]’ <= 10^9
Time Limit: 1 sec

What I have tried:

My Code:

int mod = 1e9+7;
long long solve(vector <int> &a,int k,int i,int l,int last){
    if(i==0){
        if(l>1) return 1;
        else return 0;
    }
    else{
        if(last==-1 || ((a[last-1]+a[i-1])%k==0)){
            return(solve(a,k,i-1,l+1,i)%mod + solve(a,k,i-1,l,last)%mod)%mod;
        }else{
            return solve(a,k,i-1,l,last)%mod;
        }
    }
}
long long kDivsibleSubsequences(int n, int k, vector <int> &a){
    return solve(a,k,n,0,-1)%mod;
}

l = length of the current subsequence.
last = last element that we picked from the vector

I thought of a recursive solution with memoization for further optimisation, but after I wrote my code I was stuck with 3 changing variables(i,l,last) in the recursion which means a 3-D dp which wasn't possible due to the constraints.

As I'm a begineer in DP, coming up directly with a bottom-up approch is not feasible for me in such a short time, can someone pls let me know if there is a way to memoize such questions or will I have to come up with a bottom-up solution.

PS- Thanks in advance :)