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-ի։