题目描述

小红有一个汉诺塔的模型，但是他不喜欢用它来玩汉诺塔。

于是他制作了一些大小相同的圆盘，每个圆盘上标了一个数字。他往两边的柱子上放入了 $n$ 个圆盘，你可以看到左边的第 $i$ 个（从上往下）圆盘上写了个数字 $a_i$ ，右边的圆盘上写了个数字 $b_i$ 。每次，小红会拿出左右两根柱子上最上面的圆盘，你可以指挥小红选择左边还是右边的圆盘放到中间的柱子上。你的目标是使中间的圆盘上的数字之和是3的倍数。

这个玩法也非常有趣，因为每天做出一个方案也有可能会做到世界毁灭那天。

现在你能算出有多少方案吗?当然，小红想知道的是对$10^9+7$取模后的答案.

输入描述

第一行输入一个正整数$n$，代表圆盘数量。($1<=n<=10^5$)

接下来的$n$行，每行输入两个正整数$a_i$和$b_i$，代表左边和右边的第$i$个圆盘的数字.($1<=a_i,b_i<=10^9$)

输出描述

一个整数，代表方案数对$10^9+7$取模的值

样例

样例输入

3
1 3
2 2
3 1

样例输出

4