Lista de probleme 3

Pentru o permutare p1, p2, …, pN a numerelor de la 1 la N și o poziție K, (1 ≤ K ≤ N), notăm cu BestK numărul minim de interschimbări (a valori situate pe poziții consecutive) necesare pentru a se obține o permutare descrescătoare de la poziția 1 la poziția K și crescătoare de la poziția K la poziția N. Se dă o permutare. Se cere să se rezolve una dintre următoarele două cerințe:
1. Pentru o poziție K dată să se calculeze BestK.
2. Pentru toate pozițiile K de la 1 la N să se calculeze BestK.

Plictisit de filantropie și produs cipuri, William Poartă și-a găsit o nouă pasiune: anchetele epidemiologice. Astfel, el s-a gândit să cerceteze răspândirea unui virus din trecut asupra omenirii, formată din N persoane. William știe pentru fiecare om starea sa finală (infectat sau neinfectat), însă nu știe care dintre oameni au fost infectați inițial, și care au fost infectați de la alte persoane. Acum William își pune următoarele întrebări:
1. Pentru fiecare om, poate acesta să fie unul dintre cei infectați inițial?
2. Pentru fiecare om, poate acesta să fie unul dintre cei neinfectați inițial?

Se dau N cuvinte formate doar din primele K litere mici ale alfabetului englez și un șir xi de M numere naturale. Trebuie să se formeze M cuvinte astfel încât oricare cuvânt i (1 ≤ i ≤ M) să respecte
următoarele proprietăți:

• Să aibă lungimea xi
• Să fie format doar din primele K litere mici ale alfabetului englez
• Să nu existe niciun cuvânt cuv din cele N date inițial sau din celelalte M - 1 nou formate astfel încât cuv să fie prefix al cuvântului i
• Să nu existe niciun cuvânt cuv din cele N date inițial sau din celelalte M - 1 nou formate astfel încât cuvântul i să fie prefix al lui cuv

Să se calculeze numărul de moduri de a forma M cuvinte care respectă proprietățile de mai sus. Două moduri se consideră diferite dacă există cel puțin o poziție i pentru care al i-lea cuvânt diferă. Deoarece acest număr poate fi foarte mare, se va afișa doar restul său la împărțirea cu 1.000.000.007.