Editing 3821 - Magic Digits

==Cerința==
Le Quack , mare fan al Lord Of The Rings , dar și al vrăjitoriei , află de la Gandalf că cifrele magice sunt { 1,2,3,4,5,6,7,8,9 } , cifra 0 este prea asemănătoare cu ochiul lui Sauron , fiind astfel considerată malefica. Le Quack iubeste aceste cifre magice încât le-a studiat mai atent și a observat că acestea pot forma numere de diferite lungimi ( ex : 1124 , 312 , 91235 ). Pentru fiecare număr format cu cifre magice definim gradul de frumusete ca fiind suma dintre frecvența minima a unei cifre magice și frecvența maxima a unei cifre magice care se găsește în număr. Formal , dacă construim un vector f , unde f[i] este numărul de apariții ale cifrei i și se șterg toate valorile pentru care f[i] = 0 , atunci min(f) + max(f) = k , unde k este gradul de frumusețe al numărului. De exemplu , pentru numărul 131 gradul de frumusețe este 1+2 = 3. Le Quack își pune următoarea întrebare : Câte numere de n cifre au gradul de frumusețe egal cu k ?

==Date de intrare==
Programul citește de la tastatură pe prima linie un număr N reprezentând lungimea numerelor care trebuie numărate și k , gradul de frumusețe al lor.

==Date de ieșire==
Programul va afișa pe ecran numărul cerut modulo 666013.

==Restricții și precizări==
N <= 300.
K <= 2*N.
Pentru 10 puncte N <= 6.
Pentru alte 10 puncte , K > N.
Pentru restul de 80 de puncte , K <= N , N > 6 si N <= 300.
Nu uitați că cifra 0 nu poate fi folosită !
==Exemplu==:
Intrare

2 2
Ieșire

72
Intrare

3 2
Ieșire

504
==Explicație==
În primul exemplu , sunt 72 de numere de lungime 2 cu gradul de frumusețe 2. câteva dintre acestea
sunt : 13 , 14 , 32.
În al doilea exemplu sunt 504 numere de lungime 3 cu gradul de frumusețe 2. Câteva dintre acestea
sunt : 132 , 152 , 512.
==Rezolvare==
MOD = 666013

def numere_grad_frumusete(N, k):
    # Funcție auxiliară pentru calculul coeficientului binomial
    def comb(n, r):
        result = 1
        for i in range(r):
            result = (result * (n - i)) % MOD
            result = (result * pow(i + 1, MOD - 2, MOD)) % MOD
        return result

    # Funcție recursivă pentru generarea numărului de aranjamente
    def count_arrangements(digit_counts, current_k):
        if current_k < 0:
            return 0
        if current_k == 0:
            # Calculăm numărul de moduri în care putem aranja cifrele
            result = 1
            for count in digit_counts:
                result = (result * comb(N, count)) % MOD
            return result

        total_arrangements = 0
        for i in range(1, 10):
            # Adăugăm cifra i și continuăm recursiv
            new_digit_counts = digit_counts[:]
            new_digit_counts.append(i)
            total_arrangements = (total_arrangements + count_arrangements(new_digit_counts, current_k - 1)) % MOD

        return total_arrangements

    return count_arrangements([], k)

if __name__ == "__main__":
    # Citim datele de intrare
    N, k = map(int, input().split())

    # Calculăm rezultatul și afișăm rezultatul modulo MOD
    rezultat = numere_grad_frumusete(N, k)
    print(rezultat)
python grad_frumusete.py