题目背景

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$。

本题采用捆绑测试。

对于所有数据，保证 $1\le n\le2\times10^5$，$1\le a_i\le10^9$，$1\le v_i\le10^9$。