2007 : Writing
Problem type : Batch
Time limit : 3.0 second(s)
Memory limit : 32 megabyte(s)
การถอดรหัสข้อความภาษามายันนั้นยากลำบากกว่าที่นักบุกเบิกยุคแรกๆ คิดไว้  หลังการค้นคว้าเกือบสองร้อยปี ภาษานี้ก็ยังเป็นที่เข้าใจได้น้อยมาก  ความก้าวหน้าที่แท้จริงเพิ่งจะเกิดขึ้นเมื่อสามทศวรรษที่ผ่านมานี้เอง

ในการเขียนภาษามายันนั้นจะใช้กลุ่มสัญลักษณ์ที่เรียกว่า “กลิฟ” (glyph) ซึ่งจะแทนเสียงต่างๆ   คำในภาษามายันจะเขียนโดยใช้กลิฟหลายๆ ตัวนำมาเขียนต่อกันในตำแหน่งต่างๆ

ปัญหาหนึ่งในการถอดรหัสข้อความมายันเกี่ยวข้องกับลำดับของการอ่าน  ในการเขียนกลิฟหลายๆ ตัว เพื่อประกอบเป็นคำหนึ่งคำขึ้นมานั้น นักเขียนชาวมายันสามารถเลือกตำแหน่งในการเขียนตามอารมณ์สุนทรีย์ของตนโดยไม่จำเป็นต้องคำนึงถึงกฎเกณฑ์ใด ๆ   การขาดกฏเกณฑ์นี้สร้างปัญหาแก่นักโบราณคดีโดยทำให้เกิดความสับสนในการอ่านคำที่เขียนออกมาทั้งๆ ที่ทราบวิธีการออกเสียงกลิฟต่างๆ แล้ว
นักโบราณคดีต้องการค้นหาคำพิเศษ W  เขาทราบกลุ่มของกลิฟที่ประกอบเป็นคำนี้ แต่ว่าไม่ทราบวิธีการเรียงต่อกันทั้งหมดที่เป็นไปได้   เนื่องจากเขาทราบว่าคุณมาแข่ง IOI’06  เขาจึงขอร้องให้คุณช่วย  เขาจะให้กลิฟ g ตัวของคำ W และลำดับ S ของกลิฟทั้งหมดตามลำดับที่ปรากฏในแผ่นบันทึกที่เขากำลังศึกษา  ให้คุณช่วยเขาโดยการนับจำนวนครั้งของการปรากฏที่เป็นไปได้ของคำ W 

งานของคุณ
เขียนโปรแกรมที่รับกลิฟของ W และลำดับ S ของกลิฟในแผ่นบันทึก  จากนั้นจงนับจำนวนการปรากฏที่เป็นไปได้ทั้งหมดของ W ใน S   นั่นคือให้นับทุก ๆ ลำดับที่ต่อเนื่องกันของกลิฟ  g ตัวใน S  ที่เป็นการเรียงสับเปลี่ยน (permutation) ของ กลิฟใน W

เงื่อนไข
1 ≤ g ≤ 3000 จำนวนกลิฟใน W
g ≤ |S| ≤ 3 000 000 โดยที่ |S| แทนจำนวนกลิฟในลำดับ S

ข้อมูลนำเข้า
บรรทัดที่ 1: มีจำนวนเต็มสองจำนวนที่คั่นด้วยช่องว่าง แทน g และ |S|
บรรทัดที่ 2: มีอักขระ g ตัวติดต่อกันแทนกลิฟใน W  อักขระที่เป็นไปได้คือ ‘a’-‘z’ และ ‘A’-‘Z’  อักขระพิมพ์ใหญ่และอักขระพิมพ์เล็กจะถือว่าแตกต่างกัน
บรรทัดที่ 3: มีอักขระ |S| ตัวติดต่อกันที่แสดงกลิฟในแผ่นบันทึก อักขระที่เป็นไปได้คือ ‘a’-‘z’ และ ‘A’-‘Z’  อักขระพิมพ์ใหญ่และอักขระพิมพ์เล็กจะถือว่าแตกต่างกัน

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

บรรทัดที่ 1: จะต้องมีจำนวนครั้งที่เป็นไปได้ที่ W ปรากฏใน S

ที่มา: International Olympiad in Informatics 2006 Maxico

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
4 11
cAda
AbrAcadAbRa
2

ความช่วยเหลือ: Hint[1]  

กำลังออนไลน์: 23 ผู้เยี่ยมชมและ 1 สมาชิก (1 บอท)