{"problem":{"name":"Graph Smoothing","description":{"content":"We have a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$ and the edges are numbered $1$ through $M$.   Edge $i$ connects Vertex $X_i$ and Vertex $Y_","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc199_f"},"statements":[{"statement_type":"Markdown","content":"We have a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$ and the edges are numbered $1$ through $M$.  \nEdge $i$ connects Vertex $X_i$ and Vertex $Y_i$. Initially, Vertex $i$ has an integer $A_i$ written on it.  \nYou will do the following operation $K$ times:\n\n*   Choose one from the $M$ edges uniformly at random and independently from other choices. Let $x$ be the arithmetic mean of the numbers written on the two vertices connected by that edge. Replace each number written on those vertices with $x$.\n\nFor each vertex $i$, find the expected value of the number written on that vertex after $K$ operations, and print it modulo $(10^9 + 7)$ as described in Notes.\n\n## Constraints\n\n*   $2 \\le N \\le 100$\n*   $1 \\le M \\le \\frac{N(N - 1)}{2}$\n*   $0 \\le K \\le 10^9$\n*   $0 \\le A_i \\le 10^9$\n*   $1 \\le X_i \\le N$\n*   $1 \\le Y_i \\le N$\n*   The given graph is simple.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$A_1$ $A_2$ $A_3$ $\\dots$ $A_N$\n$X_1$ $Y_1$\n$X_2$ $Y_2$\n$X_3$ $Y_3$\n$\\hspace{15pt} \\vdots$\n$X_M$ $Y_M$\n\n[samples]\n\n## Notes\n\nWhen printing a rational number, first, represent it as a fraction $\\frac{y}{x}$, where $x$ and $y$ are integers and $x$ is not divisible by $(10^9+7)$ (under the Constraints of this problem, such a representation is always possible).  \nThen, print the only integer $z$ between $0$ and $(10^9+6)$ (inclusive) such that $xz \\equiv y \\pmod {10^9+7}$.","is_translate":false,"language":"English"}],"meta":{"iden":"abc199_f","tags":[],"sample_group":[["3 2 1\n3 1 5\n1 2\n1 3","3\n500000005\n500000008\n\n*   If Edge $1$ is chosen in the only operation: the vertices written on Vertices $1, 2, 3$ will be $2, 2, 5$, respectively.\n*   If Edge $2$ is chosen in the only operation: the vertices written on Vertices $1, 2, 3$ will be $4, 1, 4$, respectively.\n\nThus, the expected values of the numbers written on Vertices $1, 2, 3$ are $3, \\frac{3}{2}, \\frac{9}{2}$, respectively.  \nIf we express them modulo $(10^9 + 7)$ as described in Notes, they will be $3, 500000005, 500000008$, respectively."],["3 2 2\n12 48 36\n1 2\n1 3","750000036\n36\n250000031\n\n*   If Edge $1$ is chosen in the $1$\\-st operation: The numbers written on Vertices $1, 2, 3$ will be $30, 30, 36$, respectively.\n    *   If Edge $1$ is chosen in the $2$\\-nd operation: The numbers written on Vertices $1, 2, 3$ will be $30, 30, 36$, respectively.\n    *   If Edge $2$ is chosen in the $2$\\-nd operation: The numbers written on Vertices $1, 2, 3$ will be $33, 30, 33$, respectively.\n*   If Edge $2$ is chosen in the $1$\\-st operation: The numbers written on Vertices $1, 2, 3$ will be $24, 48, 24$, respectively.\n    *   If Edge $1$ is chosen in the $2$\\-nd operation: The numbers written on Vertices $1, 2, 3$ will be $36, 36, 24$, respectively.\n    *   If Edge $2$ is chosen in the $2$\\-nd operation: The numbers written on Vertices $1, 2, 3$ will be $24, 48, 24$, respectively.\n\nEach of these four scenarios happen with probability $\\frac{1}{4}$, so the expected values of the numbers written on Vertices $1, 2, 3$ are $\\frac{123}{4}, \\frac{144}{4} (=36), \\frac{117}{4}$, respectively."],["4 5 1000\n578 173 489 910\n1 2\n2 3\n3 4\n4 1\n1 3","201113830\n45921509\n67803140\n685163678"]],"created_at":"2026-03-03 11:01:13"}}