أنت تحب المعكرونة كثيراً، وتقوم بطهيها وتناولها على العشاء كل يوم. يمكنك تحضير $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$.