Editing 3828 - D Caesar Queries

==Cerința==
După ce Julius Caesar l-a învins pe Pompey în bătălia de la Pharsalus , acesta decide să țină un festin în cinstea soldaților săi loilai . El are q scenarii posibile pt oaspeți definite printr o pereche (n,k) care înseamnă că fiecare dintre cei n invitați pot alege unul dintre cele k feluri de mâncare . Deoarece Julius Caesar a plătit cei mai buni bucătari pentru a prepara mancarea , el își dorește ca fiecare fel de mâncare să fi fost ales de minimum un invitat. O configurație este un șir de n numere a , al i-lea soldat a ales felul a(i) . Câte configurații distincte există care să îndeplinească cerințele marelui Julius Caesar ? Două șiruri sunt distincte dacă diferă prin cel puțin o poziție.

==Date de intrare==
Fișierul de intrare caesar.in conține pe prima linie un număr q care reprezintă numărul de scenarii la care trebuie să răspundeți urmate de q linii , pe fiecare aflându-se o pereche (n , k) reprezentatnd numărul de invitați , respectiv numărul de feluri de mâncare disponibile.

==Date de ieșire==
Fișierul de ieșire caesar.out conține pe q linii răspunsul pentru fiecare scenariu modulo 666013.

==Restricții și precizări==
Q <= 100.000 , N <= 2000 K <= 2000 pentru orice query.
Pentru 20 puncte  Q = 1.
Pentru alte 20 de puncte  N , K <= 200.
Exemplu:
caesar.in

1
2 2
caesar.out

2
caesar.in

1
5 4
caesar.out

240
==Explicație==
În primul exemplu , dacă notăm cu 1 primul fel de mâncare și cu 2 al doilea fel de mâncare , atunci configurațiile bune sunt : 12 și 21 ( primul soldat poate alege ori primul ori al doilea fel de mâncare , iar al doilea alege felul de mâncare pe care nu l-a ales primul soldat pentru că toate felurile de mâncare să fie alese de cel puțin un soldat )
==Rezolvare==
MOD = 666013

def numar_configuratii(n, k):
    total_aranjamente = pow(k, n, MOD)
    aranjamente_fara_un_fel = pow(k-1, n, MOD)

    rezultat = (total_aranjamente - aranjamente_fara_un_fel) % MOD
    return rezultat

if __name__ == "__main__":
    # Citim numărul de scenarii
    q = int(input())

    # Pentru fiecare scenariu, citim valorile și calculăm rezultatul
    for _ in range(q):
        n, k = map(int, input().split())
        rezultat = numar_configuratii(n, k)
        print(rezultat)
python caesar.py