{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input 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$"},{"iden":"sample input 1","content":"3 2\n1\n2\n3\n1 2\n1 3"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"5 3\n3\n2\n3\n1\n4\n1 5\n2 3\n4 2"},{"iden":"sample output 2","content":"36"},{"iden":"sample input 3","content":"9 5\n3\n1\n4\n1\n5\n9\n2\n6\n5\n3 5\n8 9\n7 9\n3 2\n3 8"},{"iden":"sample output 3","content":"425"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}