[YDOI R1] Necklace

hdkk 正在做项链。

hdkk 有 $n$ 种颜色的珠子，每种珠子有 $a_i$ 颗，他可以选出任意颗珠子串成一串项链。 每种珠子有一个漂亮值 $v_i$，hdkk 认为项链有一个美丽度，若第 $i$ 种珠子在项链中有 $cnt$ 颗并且 $cnt\ge1$，则这串项链的美丽度会加上 $(v_i)^{cnt}$。 现在他想知道，所有不同的项链的美丽度总和是多少，请你求出答案，并对 $10^9+7$ 取模。 定义两串项链是不同的，当且仅当存在一颗珠子，它在一串项链中出现，在另一串中没有出现。 注意：每颗珠子都是互不相同的，即使颜色一样。

第 $1$ 行有 $1$ 个正整数 $n$。 第 $2$ 行有 $n$ 个整数，第 $i$ 个数表示 $a_i$。 第 $3$ 行有 $n$ 个整数，第 $i$ 个数表示 $v_i$。

一个整数，所有不同项链的美丽度的总和对 $10^9+7$ 取模的结果。

2
1 2
2 3 

38

2
18 2
9 1

786624

### 样例解释 #1 颜色 $1$：$\left\{1\right\}$，颜色 $2$：$\left\{2,3\right\}$。 共有 $7$ 种不同的项链：$\left \{1 \right \},\left \{2\right \},\left \{3\right \},\left \{1,2 \right \},\left \{1,3 \right \},\left \{2,3 \right \},\left \{1,2,3 \right \}$，美丽度总和为 $2+3+3+(2+3)+(2+3)+3^2+(2+3^2)=38$。 **本题采用捆绑测试。** |子任务编号|$n\le$|$a_i\le$|分值| |:--:|:--:|:--:|:--:| |$1$|$4$|$5$|$15$| |$2$|$10^3$|$10^3$|$25$| |$3$|$2\times10^5$|$10^9$|$60$| 对于所有数据，保证 $1\le n\le2\times10^5$，$1\le a_i\le10^9$，$1\le v_i\le10^9$。