אתם אוהבים מאוד פסטה, ובכל יום אתם מכינים ואוכלים פסטה לארוחת ערב. אתם יודעים להכין $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$.