คุณชอบพาสต้ามาก และทำพาสต้ากินเป็นอาหารเย็นทุกวัน คุณสามารถทำพาสต้าได้ $3$ ชนิด คือ ซอสมะเขือเทศ ซอสครีม และซอสโหระพา (เพสโต้)

คุณตัดสินใจวางแผนรายการอาหารเย็นสำหรับ $N$ วัน ในแต่ละวันคุณจะเลือกพาสต้า $1$ ชนิดจาก $3$ ชนิด อย่างไรก็ตาม หากกินพาสต้าชนิดเดียวกันติดต่อกันจะทำให้เบื่อ จึงห้ามเลือกพาสต้าชนิดเดียวกันติดต่อกันตั้งแต่ $3$ วันขึ้นไป นอกจากนี้ พาสต้าของ $K$ วันจากทั้งหมด $N$ วันได้ถูกกำหนดไว้เรียบร้อยแล้ว

เมื่อกำหนดค่าของ $N$ และข้อมูลพาสต้าของ $K$ วันมาให้ จงเขียนโปรแกรมเพื่อหาเศษเหลือจากการหารจำนวนแผนการที่สอดคล้องกับเงื่อนไขด้วย $10000$

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

ข้อมูลนำเข้าประกอบด้วย $K + 1$ บรรทัด

บรรทัดที่ $1$ มีจำนวนเต็ม $2$ จำนวนคือ $N, K$ ($3 \le N \le 100$, $1 \le K \le N$) คั่นด้วยช่องว่าง

บรรทัดที่ $(1 + i)$ ($1 \le i \le K$) มีจำนวนเต็ม $2$ จำนวนคือ $A_i, B_i$ ($1 \le A_i \le N$, $1 \le B_i \le 3$) คั่นด้วยช่องว่าง ซึ่งหมายความว่าพาสต้าของวันที่ $A_i$ ได้ถูกกำหนดไว้แล้ว โดยเมื่อ $B_i = 1$ คือซอสมะเขือเทศ เมื่อ $B_i = 2$ คือซอสครีม และเมื่อ $B_i = 3$ คือซอสโหระพา ค่า $A_i$ ($1 \le i \le K$) ทั้งหมดแตกต่างกัน ในข้อมูลนำเข้าที่กำหนดให้ รับประกันว่ามีแผนการที่สอดคล้องกับเงื่อนไขอย่างน้อย $1$ แบบ

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

แสดงเศษเหลือจากการหารจำนวนแผนการที่สอดคล้องกับเงื่อนไขด้วย $10000$ ในบรรทัดเดียว

ตัวอย่างข้อมูลนำเข้าและส่งออก

ตัวอย่างข้อมูลนำเข้า 1

5 3
3 1
1 1
4 2

ตัวอย่างข้อมูลส่งออก 1

6

ในตัวอย่างที่ $1$ คุณวางแผนสำหรับ $5$ วัน วันที่ $1$ และวันที่ $3$ เป็นซอสมะเขือเทศ และวันที่ $4$ เป็นซอสครีม นอกจากนี้ ห้ามเลือกพาสต้าชนิดเดียวกันติดต่อกันตั้งแต่ $3$ วันขึ้นไป มีแผนการที่สอดคล้องกับเงื่อนไขเหล่านี้ $6$ แบบ

ในตารางนี้ $1$ แทนซอสมะเขือเทศ $2$ แทนซอสครีม และ $3$ แทนซอสโหระพา

ตัวอย่างข้อมูลนำเข้า 2

20 5
10 2
4 3
12 1
13 2
9 1

ตัวอย่างข้อมูลส่งออก 2

2640

ในตัวอย่างที่ $2$ มีแผนการที่สอดคล้องกับเงื่อนไขทั้งหมด $4112640$ แบบ จึงแสดงผลเป็น $2640$ ซึ่งเป็นเศษเหลือจากการหารด้วย $10000$