SPOJ in Armenian

2 × n չափի վանդակավոր տախտակը հարկավոր է ծածկել 1 × 2 չափի և 1 × 1 չափի սալիկներով։ Ընդ որում 1 × 2 չափի սալիկները թույլատրվում է պտտել 90 աստիճանով։  Որոշ տեղեր արդեն տեղադրված են 1 × 1 չափի սալիկներ։ Հարկավոր է հաշվել, թե մնացած ազատ վանդակները քանի եղանակով է հնարավոր ծածկել։ Պատասխանը պետք է արտածել ըստ մոդուլ 10⁹ + 7-ի։

Մուտք

 Առաջին տողում տրված են տախտակի n երկարությունը և տեղադրված սալիկների k քանակը (1 ≤ n ≤ 100 000, 1 ≤ k < 2n)։ Հաջորդ k տողերից յուրաքանչյուրը պարունակում է երկու xi և yi թվեր, որոնք ցույց են տալիս դրված սալիկների կոորդինատները (1 ≤ xi ≤ n, 1 ≤ yi ≤ 2)։

Ելք

Պետք է արտածել ծածկույթների քանակը  ըստ մոդուլ 10⁹ + 7-ի։

Օրինակ

Մուտք.

3 1
2 1

ելք.

8