output_description: Print the sum of the inversion numbers of the final sequences, modulo 10^9+7.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N Q
      A_1
      :
      A_N
      X_1 Y_1
      :
      X_Q Y_Q
attempt: def selection(elems, low, high):
      num_swap = 0
      ns_l = 0
      ns_r = 0
      if low < high:
          pos, num_swap = partition(elems, low, high)
          ns_l = selection(elems, low, pos - 1)
          ns_r = selection(elems, pos + 1, high)
      return num_swap + ns_l + ns_r
  
  
  def partition(elems, low, high):
      pivot = elems[low]
      num_swap = 0
      lower_end = low
      i = low + 1
      while i <= high:
          if elems[i] < pivot:
              tmp = elems[lower_end]
              elems[lower_end] = elems[i]
              elems[i] = tmp
              # if(i != higher_start):
              num_swap += 1
              lower_end += 1
          i += 1
      elems[lower_end] = pivot
  
      return lower_end, num_swap
  
  
  def swap_list(dl, idx1, idx2):
      tmp = dl[idx1]
      dl[idx1] = dl[idx2]
      dl[idx2] = tmp
  
  
  def dec2binary(dec):
      q = dec // 2
      r = dec % 2
      binary_list = [r]
      while q != 0:
          r = q % 2
          q = q // 2
          binary_list.append(r)
      return binary_list  # get the reserved binary_list
  
  
  def main():
      N, Q = [int(each) for each in input().split()]
      dl = []
  
      operation = []
      for i in range(N):
          dl.append(int(input().strip()))
      for i in range(Q):
          operation.append([int(each) for each in input().split()])
      print("dl ", dl)
      total_num = 0
      for i in range(2**Q):
          valid_opr = dec2binary(i)
          swap_dl = []
          for m in range(N):
              swap_dl.append(dl[m])
  
          for j in range(len(operation)):
              idx1 = operation[j][0] - 1
              idx2 = operation[j][1] - 1
              if j < len(valid_opr) and valid_opr[j] == 1:
                  swap_list(swap_dl, idx1, idx2)
              elif j >= len(valid_opr):
                  break
          tmp_num = selection(swap_dl, 0, len(swap_dl) - 1)
          # print('for {} , the inversion num {}'.format(swap_dl , tmp_num))
          total_num += tmp_num
      print(total_num)
      return total_num
  
  
  if __name__ == "__main__":
      main()
  
problem_description: Statement
  
  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:
  
    * Swap the values of A_{X_i} and A_{Y_i}
    * Do nothing
  
  There 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.
  
  Here, 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.
samples: [{"input": "3 2\n    1\n    2\n    3\n    1 2\n    1 3", "output": "6\n    \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.\n\n* * *"}, {"input": "5 3\n    3\n    2\n    3\n    1\n    4\n    1 5\n    2 3\n    4 2", "output": "36\n    \n\n* * *"}, {"input": "9 5\n    3\n    1\n    4\n    1\n    5\n    9\n    2\n    6\n    5\n    3 5\n    8 9\n    7 9\n    3 2\n    3 8", "output": "425"}]