{"problem":{"name":"Inversion Sum","description":{"content":"You are given an integer sequence of length $N$: $A_1,A_2,...,A_N$. Let us perform $Q$ operations in order. The $i$\\-th operation is described by two integers $X_i$ and $Y_i$. In this operation, we wi","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc030_d"},"statements":[{"statement_type":"Markdown","content":"You are given an integer sequence of length $N$: $A_1,A_2,...,A_N$. Let us perform $Q$ operations in order. The $i$\\-th operation is described by two integers $X_i$ and $Y_i$. In this operation, we will choose one of the following two actions and perform it:\n\n*   Swap the values of $A_{X_i}$ and $A_{Y_i}$\n*   Do nothing\n\nThere are $2^Q$ ways to perform these operations. Find the sum of the inversion numbers of the final sequences for all of these ways to perform operations, modulo $10^9+7$.\nHere, the inversion number of a sequence $P_1,P_2,...,P_M$ is the number of pairs of integers $(i,j)$ such that $1\\leq i < j\\leq M$ and $P_i > P_j$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 3000$\n*   $0 \\leq Q \\leq 3000$\n*   $0 \\leq A_i \\leq 10^9(1\\leq i\\leq N)$\n*   $1 \\leq X_i,Y_i \\leq N(1\\leq i\\leq Q)$\n*   $X_i\\neq Y_i(1\\leq i\\leq Q)$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $Q$\n$A_1$\n$:$\n$A_N$\n$X_1$ $Y_1$\n$:$\n$X_Q$ $Y_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc030_d","tags":[],"sample_group":[["3 2\n1\n2\n3\n1 2\n1 3","6\n\nThere are four ways to perform operations, as follows:\n\n*   Do nothing, both in the first and second operations. The final sequence would be $1,2,3$, with the inversion number of $0$.\n*   Do nothing in the first operation, then perform the swap in the second. The final sequence would be $3,2,1$, with the inversion number of $3$.\n*   Perform the swap in the first operation, then do nothing in the second. The final sequence would be $2,1,3$, with the inversion number of $1$.\n*   Perform the swap, both in the first and second operations. The final sequence would be $3,1,2$, with the inversion number of $2$.\n\nThe sum of these inversion numbers, $0+3+1+2=6$, should be printed."],["5 3\n3\n2\n3\n1\n4\n1 5\n2 3\n4 2","36"],["9 5\n3\n1\n4\n1\n5\n9\n2\n6\n5\n3 5\n8 9\n7 9\n3 2\n3 8","425"]],"created_at":"2026-03-03 11:01:14"}}