กษัตริย์ราเมสเซสที่สองเพิ่งได้รับชัยชนะจากสงคราม พระองค์ได้ตัดสินใจที่จะสร้างสวนหลวงขึ้นแห่งหนึ่งเพื่อสร้างที่ระลึกแห่งชัยชนะ  สวนแห่งนี้จะประกอบด้วยแนวของต้นไม้จากพระราชวังที่ลุกซอร์มายังวิหารแห่งคาร์นัก โดยต้นไม้จะมีเพียง ต้นบัว (Lotus) และ ต้นกก (Papyrus) เนื่องจากว่าต้นไม้ทั้งสองเป็นสัญลักษณ์ของส่วนบนและส่วนล่างของอียิปต์ตามลำดับ

ในสวนจะมีต้นไม้ทั้งหมด N ต้น และต้องสมดุลย์ นั่นคือทุกส่วนย่อยที่อยู่ติดกันของสวนจะต้องมีจำนวนของต้นบัวและต้นกก แตกต่างไม่เกินสองต้น

สวนหลวงนี้สามารถเขียนแทนด้วยสตริงที่ประกอบด้วยตัวอักษร ‘L’ แทนต้นบัว และ ‘P’ แทนต้นกก ตัวอย่างเช่น กรณีที่ N=5 จะมีสวนที่สมดุลย์ที่เป็นไปได้ทั้งหมด ๑๔ แบบเรียงตามลำดับตัวอักษรเป็นดังนี้ LLPLP, LLPPL, LPLLP, LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP, และ PPLPL

รูปแบบของสวนสมดุลย์ทั้งหมดในขนาดหนึ่ง ๆ สามารถนำมาเรียงลำดับตามตัวอักษรและให้หมายเลขกับรูปแบบเหล่านั้น โดยรูปแบบแรกจะได้หมายเลข 1   ตัวอย่างเช่น กรณีที่ N=5 รูปแบบของสวนหมายเลข 12 คือ PLPPL

โจทย์

จงเขียนโปรแกรมเพื่ออ่านค่าจำนวนต้นไม้ N ต้นและสตริงหนึ่งสตริงที่แทนรูปแบบสวนที่สมดุลย์  จากนั้นคำนวณหาหมายเลขของสวนสมดุลย์นั้นโดยตอบเป็นผลหารเอาเศษด้วยจำนวนเต็ม M

สังเกตว่า ในการแก้ปัญหาโจทย์นี้ ค่า M ไม่มีความสำคัญใดนอกไปจากทำให้การคำนวณง่ายขึ้น

เงื่อนไข

1<=N<=1,000,000

7<=M<=10,000,000

การให้คะแนน

มีชุดทดสอบที่มีคะแนนรวม 40 คะแนน สำหรับ N ไม่เกิน 40

ข้อมูลนำเข้า

โปรแกรมของคุณต้องอ่านข้อมูลนำเข้าต่อไปนี้จาก standard input

·        บรรทัดที่ ๑  มีค่าจำนวนเต็ม N ซึ่งเป็นจำนวนต้นไม้ทั้งหมดในสวน

·        บรรทัดที่ ๒ มีค่าจำนวนเต็ม M

·    บรรทัดที่ ๓ มีสตริงหนึ่งสตริงความยาว N  ตัวอักษรที่ประกอบด้วยอักษร ‘L’ (แทนต้นบัว) หรือ ‘P’ (แทนต้นกก) ซึ่งแทนสวนสมดุลย์แบบหนึ่ง

ข้อมูลส่งออก

โปรแกรมของคุณต้องแสดงผลลัพธ์ออกทาง standard output โดยจะมีเพียงบรรทัดเดียวโดยจะเป็นจำนวนเต็มหนึ่งจำนวนที่มีค่าตั้งแต่ 0 ถึง M-1 ซึ่งก็คือ หมายเลขของสวนดุลย์ตามที่อ่านได้จากข้อมูลนำเข้าหารเอาเศษด้วย M

ที่มา: 20^th International Olympiad in Informatics; Cairo, Egypt (Day 2)