Un copil dorește să vopsească ouăle de Paște, având la dispoziție vopsele de culoare roșie, galbenă, verde și albastră. Fiecare culoare va fi reprezentată printr-un singur caracter astfel: ′r′ pentru culoarea roșie, ′g′ pentru galben, ′v′ pentru verde, ′a′ pentru albastru. Pentru a vopsi ouăle, le așază în rând, unul după altul. Astfel, o colorare va fi o succesiune de N caractere din mulţimea {′r′,′g′,′v′,′a′}, reprezentând, în ordinea aşezării, culorile celor N ouă.
Numim “roua” o secvență de R caractere cu proprietatea că dintre acestea exact R-1 caractere reprezintă culoarea roșie, iar un caracter reprezintă una dintre celelalte 3 culori. De exemplu secvenţele roua de lungime 3 sunt ″grr″, ″rgr″, ″rrg″, ″vrr″, ″rvr″, ″rrv″,″arr″, ″rar″, ″rra″.
Copilul consideră că o colorare este R-frumoasă, dacă oricare R caractere consecutive din colorare formează o secvență roua. De exemplu, pentru N=11 ouă, şirul ″arrrvrrrarr″ reprezintă o colorare 4-frumoasă.
Cerinţă
Cunoscând N, numărul de ouă vopsite, și numărul natural R, scrieți un program care determină și afișează:
1. numărul de secvențe “roua” de lungime R existente în colorarea celor N ouă;
2. numărul total al colorărilor R-frumoase pentru cele N ouă.
Date de intrare
Fișierul de intrare roua.in conține pe prima linie un număr natural C reprezentând cerința din problemă care trebuie rezolvată (1 sau 2). A doua linie din fișier conține numerele naturale N și R, separate prin spaţiu, reprezentând numărul de ouă și lungimea unei secvențe “roua”. Dacă C=1, fișierul va conţine şi o a treia linie pe care se află colorarea celor N ouă.
Date de ieşire
Fişierul de ieşire roua.out va conţine o singură linie pe care va fi scris un număr natural, reprezentând răspunsul la cerinţa specificată în fişierul de intrare.
Restricţii
• 3 ≤ N ≤ 10000
• 2 ≤ R < N
• Pentru rezolvarea corectă a cerinței 1 se acordă 40 puncte, pentru rezolvarea corectă a cerinței 2 se acordă 60 de puncte.
• Pentru 60% dintre testele pentru cerința 2, 3 ≤ N ≤ 70
• Pentru 40% dintre testele pentru cerința 2, N > 70
• Rezultatul la cerința 2 poate avea cel mult 2400 de cifre.
Exemple
roua.in
roua.out
Explicaţii
1
7 3
vrrrgrr
4
Cerinţa este 1. Există N=7 ouă. Secvențele roua de lungime 3 existente în colorare sunt ″vrr″, ″rrg″, ″rgr″, ″grr″.
2
4 3
15
Cerinţa este 2. Există 4 ouă.
Colorările 3-frumoase ale celor 4 ouă sunt ″grrg″, ″grrv″, ″grra″, ″vrrg″, ″vrrv″, ″vrra″, ″arrg″, ″arrv″, ″arra″, ″rgrr″, ″rvrr″, ″rarr″, ″rrgr″, ″rrvr″, ″rrar″.