output_description: Print the count modulo (10^9+7).
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
attempt: N, M, K = (int(s) for s in input().rstrip().split())
  
  A = [int(s) for s in input().rstrip().split()]
  B = [int(s) for s in input().rstrip().split()]
  
  i, j = (0, 0)
  sum, count = (0, 0)
  
  while sum < K:
      if (i < N) and (j < M):
          if A[i] <= B[j]:
              sum += A[i]
              i += 1
              count += 1
          else:
              sum += B[j]
              j += 1
              count += 1
      elif i < N:
          sum += A[i]
          i += 1
          count += 1
      elif j < M:
          sum += B[j]
          j += 1
          count += 1
      else:
          break
  
  if sum > K:
      count -= 1
  
  print(count)
  
problem_description: Statement
  
  Count the pairs of length-N sequences consisting of integers between 1 and M
  (inclusive), A_1, A_2, \cdots, A_{N} and B_1, B_2, \cdots, B_{N}, that satisfy
  all of the following conditions:
  
    * A_i \neq B_i, for every i such that 1\leq i\leq N.
    * A_i \neq A_j and B_i \neq B_j, for every (i, j) such that 1\leq i < j\leq N.
  
  Since the count can be enormous, print it modulo (10^9+7).
samples: [{"input": "2 2", "output": "2\n    \n\nA_1=1,A_2=2,B_1=2,B_2=1 and A_1=2,A_2=1,B_1=1,B_2=2 satisfy the conditions.\n\n* * *"}, {"input": "2 3", "output": "18\n    \n\n* * *"}, {"input": "141421 356237", "output": "881613484"}]