Egyenes kert
Nemzetközi Diákolimpia (IOI), 2008, 2. nap, 1. feladat
II. Ramszesz nemrég tért haza egy győztes csatából. Elhatározta, hogy a diadal örömére épít egy hatalmas kertet. A templomot és a palotát összekötő egyenes vonal mentén épül a díszkert, amelyet lótusz és papirusz cserjék fognak díszíteni, Felső- és Alsó-Egyiptomot szimbolizálva.
A kertben pontosan N növény sorakozik majd az út mentén. Kiegyensúlyozottnak kell lennie az elrendezésnek: a kert tetszőleges szakaszát nézve legfeljebb kettővel térhet el a lótuszok és papiruszok száma.
A kert terve leírható egy "L-P" sorozattal. Például N=5 esetén 14 kiegyensúlyozott elrendezés van: LLPLP, LLPPL, LPLLP, LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP, PPLPL.
Ezek a kódok ábécé-rendbe írva beszámozhatók, 1-től kezdve a számolást. Például N=5 esetén a 12. kert-kód: PLPPL.
Feladat
Készíts programot, amely adott N esetén egy adott kert-kódra megadja annak sorszámát modulo valamilyen M. (A modulus szerepe csak az, hogy ne kelljen nagyon nagy számokkal számolni.)
Paraméter tartomány: $1\le N \le 1000000, 7\le M \le 10000000$.
Bemenet
Az első sor N, a második pedig M értékét tartalmazza. A harmadik sorban a kérdéses kert-kód található, az "L" és "P" karaktereket nem választják el szóközök.
Kimenet
A kimenet egyetlen számból áll, az adott kód sorszámának M szerinti maradékát írja le.
Példa
| lin.in | lin.out |
| 5 7 PLPPL | 5 |
| 12 10000 LPLLPLPPLPLL | 39 |