Սալիկներով ծածկույթ
2 × n չափի վանդակավոր տախտակը հարկավոր է ծածկել 1 × 2 չափի և 1 × 1 չափի սալիկներով։ Ընդ որում 1 × 2 չափի սալիկները թույլատրվում է պտտել 90 աստիճանով։ Որոշ տեղեր արդեն տեղադրված են 1 × 1 չափի սալիկներ։ Հարկավոր է հաշվել, թե մնացած ազատ վանդակները քանի եղանակով է հնարավոր ծածկել։ Պատասխանը պետք է արտածել ըստ մոդուլ 10^9 + 7-ի։Մուտքային տվյալներ
Առաջին տողում տրված են տախտակի
n երկարությունը և տեղադրված սալիկների k քանակը (1 ≤ n ≤ 100 000, 1 ≤ k < 2n)։ Հաջորդ k տողերից յուրաքանչյուրը պարունակում է երկու xi և yi թվեր, որոնք ցույց են տալիս դրված սալիկների կոորդինատները (1 ≤ xi ≤ n, 1 ≤ yi ≤ 2)։Ելքային տվյալներ
Պետք է արտածել ծածկույթների քանակը ըստ մոդուլ
10^9 + 7-ի։Օրինակ
Մուտք | Ելք |
3 1
2 1 | 8 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB