Сіз пастаны өте жақсы көресіз және күн сайын кешкі асқа паста пісіріп жейсіз. Сіз пастаның $3$ түрін жасай аласыз: қызанақ тұздығымен, кілегей тұздығымен және насыбайгүл (базилик) тұздығымен.
Сіз $N$ күндік кешкі ас жоспарын құруды ұйғардыңыз. Әр күні пастаның $3$ түрінен $1$ түрін таңдайсыз. Алайда, бірдей паста қатарынан бола берсе жалығып кететіндіктен, $3$ немесе одан да көп күн қатарынан бірдей пастаны таңдауға болмайды. Сонымен қатар, $N$ күннің ішіндегі $K$ күннің пастасы алдын ала белгіленіп қойған.
Кіріс ретінде $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 | Күн 4 | Күн 5 | |
|---|---|---|---|---|---|
| Жоспар 1 | 1 | 2 | 1 | 2 | 1 |
| Жоспар 2 | 1 | 2 | 1 | 2 | 2 |
| Жоспар 3 | 1 | 2 | 1 | 2 | 3 |
| Жоспар 4 | 1 | 3 | 1 | 2 | 1 |
| Жоспар 5 | 1 | 3 | 1 | 2 | 2 |
| Жоспар 6 | 1 | 3 | 1 | 2 | 3 |
Бұл кестеде $1$ — қызанақ тұздығын, $2$ — кілегей тұздығын, ал $3$ — насыбайгүл тұздығын білдіреді.
Кіріс мысалы 2
20 5 10 2 4 3 12 1 13 2 9 1
Шығыс мысалы 2
2640
$2$-мысалда шарттарды қанағаттандыратын барлығы $4112640$ жоспар бар. Оны $10000$-ға бөлгендегі қалдықты, яғни $2640$ санын шығарамыз.