Problema Urale

După aventurile în Pampasul argentian, Gigel s-a odihnit câteva zile în Buenos Aires. Interacționând cu localnicii și-a descoperit două noi pasiuni, fotbalul și TikTok-ul, iar norocul a făcut ca echipa lui preferată de fotbal să fie foarte activă pe TikTok. După fiecare meci câștigat, toti suporterii reacționează cu comentarii la postările care celebrează victoria. Perspicace, Gigel a observat că toate aceste comentarii sunt compuse doar din cactere din mulțimea {U,R,A,!}. Mai mult, acestea vor păstra mereu o ordine: toate caracterele caracterle de același fel sunt grupate într-o singură secvență iar ordinea caracterelor în secvență este identică ordinii din mulțime, adică toate caracterele U sunt la început, urmate de toate caracterele R, apoi toate caracterele A, iar la final toate caracterle !. Fiecare caracter poate apărea de orice număr de ori, inclusiv niciodată, iar lungimea mesajelor poate fi oricare.

Cerință

Analizând lista comentariilor apărute la ultima postare, Gigel își pune următoarele întrebări:

1. Câte mesaje de o lungime n se pot forma astfel încât să respecte condițiile din enunț?
2. Al câtelea mesaj în ordine lexicografică este mesajul pe care îl postează Gigel?

Date de intrare

Fişierul de intrare urale.in conţine, pe prima linie, un număr natural p:

• pentru p = 1 se va rezolva doar prima cerință,
• pentru p = 2 se va rezolva a doar doua cerință.

Pentru p = 1, pe a doua linie a fișierului de intrare se va afla un număr natural n. Pentru p = 2, pe a doua linie a fișierului de intrare se va afla un sir de caractere, reprezentând un mesaj valid.

Date de ieșire

Pentru p = 1, fişierul de ieşire urale.out va conţine, pe o singură linie numărul mesajelor valide ce se pot forma de lungime n.
Pentru p = 2, pe prima linie a fișierului urale.out se va afla un număr natural reprezentând numărul de ordine al mesajului scris de Gigel în ordinea tuturor mesajelor. Mesajele sunt ordonate după lungime, iar la lungimi egale sunt ordonate lexicografic.
Pentru că rezultatele pot fi foarte mari, Gigel se mulțumește cu rezultatul modulo 666013 atât pentru p = 1 cât și pentru p = 2.

Restricții și precizări

• pentru teste în valoare de 20% din punctaj: p=1 și n <= 1000
• pentru alte teste în valoare de 30% din punctaj: p=1 și n <= 100000
• pentru teste în valoare de 20% din punctaj: p=2 și lungimea șirului <=10
• pentru alte teste în valoare de din punctaj 30%: p=2 și lungimea șirului este cel mult 50000 de caractere

Exemple