найти количество подмассивов размера K, сумма которых делится на M?

Question

Алиса имеет N монет на сумму от 0 до (N-1) . Боб хочет взять из них k монет. Но Алиса будет только давайте, если интересен набор монет K . Набор монет интересен, если их сумма делится на уникальное целое число M . Теперь Боб хочет узнать, сколько способов он может получить K монет.

Вывести результат в формате ответа% (10 ^ 9 + 7): - Три целых числа через пробел: N, K, M

Ограничения: - 1 <= N, M <= 10 ^ 3 1 < = K <= 10 ^ 2 </p>

выборочный ввод: - 4 2 2

выборочный вывод: = 2 ({1,3}, {2,4})

Я попытался решить проблему с помощью комбинаций в python библиотеках, но это привело к превышению лимита памяти . Позже я применил к нему рекурсивный метод, но это также привело к превышению ограничения времени . как для каждого частного теста потребовалось 10 se c времени.

может кто-нибудь помочь в решении этого эффективного способа. Заранее спасибо. Код метода рекурсии

cou=0
n,k,m = input().split()
out_ = solve(k,m,n)
print(out_)


def getCombinations(data,n,k,m):
    val=[0]*k
    combiUtil(data,n,k,0,val,0,m)

def combiUtil(data,n,k,ind,val,i,m):
    global cou
    if(ind==k):
        if(sum(val)%m==0):
            cou+=1
        return
    if(i>=n):
        return
    val[ind]=data[i]
    combiUtil(data,n,k,ind+1,val,i+1,m)
    combiUtil(data,n,k,ind,val,i+1,m)

def solve(k,m,n):
    global cou
    k=int(k)
    m=int(m)
    n=int(n)
    ans =0
    data = [j for j in range(1,n+1)]
    getCombinations(data,n,k,m)   
    return cou%(10**9+7)