Now Elsie creates a new undirected graph GG with N1⋅N2⋯NKvertices, each labeled by a K-tuple (j1,j2,…,jK) where 1≤ji≤Ni. In G, two vertices (j1,j2,…,jK)and (k1,k2,…,kK) are connected by an edge if for all 1≤i≤K, ji and ki are connected by an edge in Gi.
Define the distance between two vertices in G that lie in the same connected component to be the minimum number of edges along a path from one vertex to the other. Compute the sum of the distances between vertex (1,1,…,1)and every vertex in the same component as it in G, modulo 109+7.
2 2 1 1 2 4 4 1 2 2 3 3 4 4 1
4
G contains 2⋅4=8 vertices, 44 of which are not connected to vertex (1,1). There are 2 vertices that are distance 1 away from (1,1)and 1 that is distance 2 away. So the answer is 2⋅1+1⋅2=4
3 4 4 1 2 2 3 3 1 3 4 6 5 1 2 2 3 3 4 4 5 5 6 7 7 1 2 2 3 3 4 4 5 5 6 6 7 7 1
706
G contains 4⋅6⋅7=1684⋅6⋅7=168 vertices, all of which are connected to vertex (1,1,1). The number of vertices that are distance i away from (1,1,1) for each i∈[1,7] is given by the i-th element of the following array: [4,23,28,36,40,24,12].
3
4 4
1 2
2 3
3 1
3 4
6 5
1 2
2 3
3 4
4 5
5 6
7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1706