拉姆西斯(Ramesses)二世剛打勝戰回來，為了慶祝戰爭勝利，他決定建一座皇家花園。花園將由一長排的植物所組成，從他在路克索(Luxor)的皇宮一直延伸到卡納克神殿(Temple of Karnak)。而所種的植物僅由連花(lotus)及紙莎草(papyrus)二種組成，它們分別是上埃及與下埃及的象徵。

    此花園必須種植N顆植物：而且植物數必須平衡，也就是在花園的任何連續區段中蓮花與紙莎草的數量差異不能大於2。

    一個花園可以用字母L(lotus)與P(papyrus)所組成的字串表示。例如，當N=5時，有14種可能的平衡花園，依英文字母次序排序如下：

LLPLP, LLPPL, LPLLP,LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP,及 PPLPL。

    某一長度的所有可能平衡花園，可依英文字母次序排序，並從1開始編號。例如，當N=5時，編號12的花園是平衡花園PLPPL。

    給定N棵植物及一表示平衡花園的字串，請寫一個程式計算出該平衡花園的編號，並取其除以一給定整數M的餘數。

注意，M在本題中與解題無關，它只是用來簡化計算。