该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一个 $n$ 个节点的树（编号 $1\sim n$ ）。对于树上一对顶点 $(x,y)$ ，我们定义两点之间的距离为：从 $x$ 到 $y$ 的路径（简单路径）中所有边的权值的异或（ $xor$ ，$\bigoplus$）。

求所有点对之间距离的和。由于结果太大，只需要输出对 $1e9+7$ 取模的结果。

异或的定义：将两个数转换为二进制，若两个数的同一位相同，则运算的结果为0，否则为1，下面是对于这一位的全部异或情况:

$1 \bigoplus 1 = 0$

$0 \bigoplus 0 = 0$

$1 \bigoplus 0 = 1$

$0 \bigoplus 1 = 1$

若想算出$5\bigoplus3$，要先把5和3变成二进制查看，$5$是$101$，$3$是$011$，因此结果是$110$，也就是$6$

输入格式

第一行：一个数 $N$ 表示字符串的长度。（$N \leq 500000$） 第二行：一个长为 $N$ 的字符串。数据保证该字符串中只包括 $H$ 和 $G$。

输出格式

输出所有点对之间距离的和对 $1e9+7$ 取模的结果。

数据范围

对于23%的数据，$2 \le n \le 10$；

对于33%的数据，$2 \le n \le 1000$；

对于100%的数据，$2 \le n \le 2 \times 10^5, 1 \le u, v \le n, 0 \le w < 2^{60}$，保证给出的图是一棵树。

输入样例

3
1 2 1
1 3 3

输出样例

6

样例解释

全部点对为：

$(1,1) = 0,(1,2) = 1,(1,3)=3,(2,2)=0,(2,3)=(1\bigoplus3)=2,(3,3)=0$

答案是全部的总和，也就是$0+1+3+0+2+0=6$