output_description: Print the number of the different good touring plans, modulo 10^9+7.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      X_1 X_2 X_3 X_4 X_5 X_6
      Y_1 Y_2 Y_3 Y_4 Y_5 Y_6
attempt: import sys
  
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  
  N, M, *X = map(int, read().split())
  
  MOD = 10**9 + 7
  
  
  def mult(a, b, c, d, e, f):
      # (a+bx+cx^2)(d+ex+fx^2) modulo 1-4x+2x^2-x^3
      a, b, c, d, e = a * d, a * e + b * d, a * f + b * e + c * d, b * f + c * e, c * f
      b += e
      c -= 4 * e
      d += 2 * e
      e = 0
      a += d
      b -= 4 * d
      c += 2 * d
      d = 0
      a %= MOD
      b %= MOD
      c %= MOD
      return a, b, c
  
  
  # (1/x)^i modulo (1-4x+2x^2-x^3)
  M = 10**5
  A1 = [0] * (M + 1)
  a, b, c = 1, 0, 0
  for i in range(M + 1):
      A1[i] = (a, b, c)
      a, b, c = b + 4 * a, c - 2 * a, a
      a %= MOD
      b %= MOD
      c %= MOD
  
  # (1/x)^Mi modulo (1-4x+2x^2-x^3)
  A2 = [0] * (M + 1)
  a, b, c = 1, 0, 0
  d, e, f = A1[M]
  for i in range(M + 1):
      A2[i] = (a, b, c)
      a, b, c = mult(a, b, c, d, e, f)
  
  
  def power(n):
      # (1/x)^n modulo (1-4x+2x^2-x^3)
      q, r = divmod(n, M)
      a, b, c = A1[r]
      d, e, f = A2[q]
      return mult(a, b, c, d, e, f)
  
  
  X.append(N)
  
  a, b, c = 0, 1, 1
  prev_x = 0
  for x in X:
      a, b, c = mult(a, b, c, *power(x - prev_x))
      b -= a
      c -= a
      prev_x = x
  
  answer = a
  print(answer)
  
problem_description: Statement
  
  Joisino is planning on touring Takahashi Town. The town is divided into square
  sections by north-south and east-west lines. We will refer to the section that
  is the x-th from the west and the y-th from the north as (x,y).
  
  Joisino thinks that a _touring plan_ is good if it satisfies the following
  conditions:
  
    * Let (p,q) be the section where she starts the tour. Then, X_1 \leq p \leq X_2 and Y_1 \leq q \leq Y_2 hold.
  
    * Let (s,t) be the section where she has lunch. Then, X_3 \leq s \leq X_4 and Y_3 \leq t \leq Y_4 hold.
  
    * Let (u,v) be the section where she ends the tour. Then, X_5 \leq u \leq X_6 and Y_5 \leq v \leq Y_6 hold.
  
    * By repeatedly moving to the adjacent section (sharing a side), she travels from the starting section to the ending section in the shortest distance, passing the lunch section on the way.
  
  Two touring plans are considered different if at least one of the following is
  different: the starting section, the lunch section, the ending section, and
  the sections that are visited on the way. Joisino would like to know how many
  different good touring plans there are. Find the number of the different good
  touring plans. Since it may be extremely large, find the count modulo 10^9+7.
samples: [{"input": "1 1 2 2 3 4\n    1 1 2 2 3 3", "output": "10\n    \n\nThe starting section will always be (1,1), and the lunch section will always\nbe (2,2). There are four good touring plans where (3,3) is the ending section,\nand six good touring plans where (4,3) is the ending section. Therefore, the\nanswer is 6+4=10.\n\n* * *"}, {"input": "1 2 3 4 5 6\n    1 2 3 4 5 6", "output": "2346\n    \n\n* * *"}, {"input": "77523 89555 420588 604360 845669 973451\n    2743 188053 544330 647651 709337 988194", "output": "137477680"}]