roua

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țe

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 ≤ 10 \ 000$
• $2 ≤ R < N$
• Pentru rezolvarea corectă a cerinței $1$ se acordă $40$ de 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 $2 \ 400$ de cifre.

Exemplul 1

roua.in

1
7 3
vrrrgrr

roua.out

4

Explicație

Cerinţa este $1$. Există $N = 7$ ouă. Secvențele roua de lungime $3$ existente în colorare sunt vrr, rrg, rgr, grr.

Exemplul 2

roua.in

2
4 3

roua.out

15

Explicație

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.