Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
 Register new ID

A Very Easy Graph Problem

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1463    Accepted Submission(s): 572

Problem Description
An undirected connected graph has $n$ nodes and $m$ edges, The $i$-th edge¡¯s length is $2^i$. Each node $i$ has a value $a_i$, which is either $0$ or $1$. You need to calculate:

\sum_{i=1}^{n}\sum_{j=1}^{n}d(i,j)\times [a_i=1\wedge a_j=0]

$d(i,j)$ indicates the shortest distance between $i$ and $j$. $[\ ]$ is the Iverson bracket. $\wedge$ indicates $\texttt{AND}$.

Because the answer may be too large, please output the answer modulo $10^9 + 7$.

The first line contains one integer $T$($1\le T \le 8$)£¬indicating the number of test cases.

The second line contains two ingeters $n,m$($1\le n\le 10^5,1\le m\le 2\times 10^5$).

The third line contains $n$ positive integers $a_1,a_2,...,a_n(a_i = 0$ or $1$) ¡ª¡ª the value of the nodes.

The following $m$ lines contain two ingeters $u,v(1
\le u,v \le n)$, and the $i$-th line represents the i-th undirected edge¡¯s length is $2^i$, between node $u$ and $v$.

The sum of $n,m$ is no more than $2\times 10^5$.

Print a single integer¡ª¡ª the value of the answer modulo $10^9+7$.

Sample Input
1 3 2 0 1 0 3 1 3 2

Sample Output


Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2023 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2023-06-01 01:02:32, Gzip enabled