MC头上的星空大致可以视为n行n列的网格，其中有些网格已经被乌云占据。MC希望（以他的想象力）点缀他的星空，可以添加两种对象：1.想象中的小星星，占据1 * 1的格子；2.想象中的魔法月亮，占据2 * 2的格子。星星、月亮、乌云之间都不能互相重叠。MC想把没有乌云的格子全部（用星星或月亮）填满，请问有多少种不同的填法？两种方法不同当且仅当存在至少一个格子所填内容不同，不需要对通过翻转、旋转重合的方案去重（参考样例说明）

输入格式

第1行2个正整数n,m 后面m行每行2个正整数x,y，表示x行y列是乌云。多组x,y有可能有重复。

输出格式 一个整数表示非乌云的格子填满星星月亮的方案数

样例：

输入：

4 3

1 4

2 1

4 3

输出：

7