Background

Special for beginners, ^_^

Description

在acimo星球, tabris 是一名勇敢的屠龙勇士，在上绿岛屠龙前决定挑选N种装备武装自己，现在每种装备有两个，**但每种装备tabris必须选择拿一个**，**不能多也不能少**。
每件装备有自己的属性值，能给tabris属性加成。
对于不同种类的装备之间有叠加效果,如果选择多件装备,最终的属性加成为他们的乘积。
若tabris初始属性值为0，最后属性加成的期望是多少。

Format

Input

有多组测试样例，输入到文件结束。
每组测试数据的第一行包含一个正整数\(N\)，表示装备的种类数。
接下来\(N\)行，每行两个正整数\(a_i\)、\(b_i\)，表示两个不同的第\(i\)种装备的属性加成值。

\(N \in [1,10^3]\)
\(a_i,b_i \in [1,10^6]\)

Output

对于每组测试数据输出一个整数,为了方便输出最终的结果先乘\(2^N\)再对1e9+7取模后的值。

Sample 1

Input

4
1 2
3 4
5 6
7 8

Output

3465

Limitation

1s, 1024KiB for each test case.

Hint

3465 = (1*3*5*7) + (1*3*5*8) +(1*3*6*7) + (1*3*6*8) + (1*4*5*7) + (1*4*5*8) + (1*4*6*7) + (1*4*6*8) + (2*3*5*7) + (2*3*5*8) + (2*3*6*7) + (2*3*6*8) + (2*4*5*7) + (2*4*5*8) + (2*4*6*7) + (2*4*6*8) ;

Source

tabris