| Fișierul intrare/ieșire | director.in, director.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | clasică | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
| Timp de execuție pe test | 0.4 sec | Limită de memorie | 262144 KB |
| Scorul tău | N/A | Dificultate | N/A |
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Director
În Cydonia, automobilele sînt înmatriculate cu coduri formate din exact K litere mici ale alfabetului englez. Locuitorii Cydoniei își pot alege după dorință coduri de înmatriculare pentru mașinile lor. Tu ești directorul unei companii gigantice al cărei nume este un șir S format din N litere. Tocmai ai primit un bonus pentru că ai convins angajații să accepte o tăiere de salarii, așa că ți-ai cumpărat o mașină de lux. Acum dorești să-i alegi un cod folosind K litere din S, nu neapărat consecutive, dar în ordinea din S.
Îți pui întrebarea: cîte coduri distincte există?
Date de intrare
Fișierul de intrare director.in conține pe prima linie întregii N și K, separați prin spațiu. A doua linie conține șirul S terminat cu caracterul linie nouă.
Date de ieșire
În fișierul de ieșire director.out Tipăriți, pe o singură linie, răspunsul la întrebare, modulo 1.000.000.007.
Restricții
- 1 ≤
N≤ 10.000; - 1 ≤
K≤ 5.000; 1 ≤K≤N
| puncte | restricții | |
|---|---|---|
| 1 | 25 | N ≤ 25; K ≤ 10; S constă doar din caractere ‘a’, ‘b’, ‘c’ sau ‘d’ |
| 2 | 25 | N ≤ 1.000; K ≤ 10; S constă doar din caractere ‘a’, ‘b’, ‘c’ sau ‘d’ |
| 3 | 25 | N ≤ 5.000; K ≤ 1.000 |
| 4 | 25 | Fără restricții suplimentare. |
Notă: La concursul de selecție, punctajele pentru subtaskuri au fost 15, 17, 29 respectiv 39.
Exemplu
| director.in | director.out | Explicații |
|---|---|---|
| 6 2 aviato |
13 |
Codurile posibile sînt av, ai, aa, at, ao, vi, va, vt, vo, ia, it, io, to. |
| 7 3 abacaba |
17 |
Codul aba poate fi obținut în 6 feluri diferite, dar trebuie numărat o singură dată. |
