Cerință
Alex și Bogdan se plictiseau la ora de informatică, așa că au inceput să se joace un joc cu numere. În acest joc, Bogdan a scris pe o foaie un șir de numere, cu valori cumprinse între și , și i-a cerut lui Alex să aleagă o proprietate pe care șirul să o îndeplinească. Dacă șirul îndeplinește proprietatea aleasă, atunci Alex câstigă jocul, altfel Bogdan va fi desemnat castigator.
După un timp de gândire, Alex alege următoarea proprietate: "Suma oricărei subsecvență din șirul scris de Bogdan a cărei lungime este un număr prim, trebuie să fie divizibilă cu 3.". Alex nu știe cat de bună a fost alegerea sa, așa că vă roagă sa determinați numărul de șiruri pe care le-ar fi putut scrie Bogdan care să îndeplinească proprietatea aleasă de el.
Date de intrare
Pr prima linie se vor regăsi cele două valori, și , cu însemnătatea din enunț.
Date de ieșire
Pe prima linie se va afișa răspunsul la cerință, și anume numărul de șiruri diferite pe care le-ar fi putut scrie Bogdan. Deoarece acest număr poate fi foarte mare, se cere să se afișeze modulo .
Restricții și precizări
- ;
- ;
Exemplu
stdin
2 4
stdout
6
Explicație
Șirurile pe care le putea alege Bogdan sunt după cum urmează:
- ;
- ;
- ;
- ;
- ;
- .