Problem: 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.

Submission attempts (in order):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
import numpy as np
from functools import lru_cache

X = list(map(int,readline().split()))
Y = list(map(int,readline().split()))

for i in [1,3,5]:
    X[i] += 1
    Y[i] += 1

X1 = X[:2]; X2 = X[2:4]; X3 = X[4:]
Y1 = Y[:2]; Y2 = Y[2:4]; Y3 = Y[4:]

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

U = 2 * 10 ** 6 + 10
MOD = 10**9 + 7
fact, fact_inv = make_fact(U,MOD)

@lru_cache()
def make_comb(n):
    return fact[n] * fact_inv[:n+1] % MOD * fact_inv[:n+1][::-1] % MOD

answer = 0
for p in itertools.product([0,1],repeat=6):
    x1,x2,x3,y1,y2,y3 = [A[i] for A,i in zip([X1,X2,X3,Y1,Y2,Y3],p)]
    sgn = (-1) ** sum(p)
    a,b,c,d = x2-x1, x3-x2, x2-x1+y2-y1, x3-x2+y3-y2
    c += 2; d += 2; sgn = -sgn
    make_comb(c)
    make_comb(d)
    

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,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


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


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):
    
    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)

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
import numpy as np
from functools import lru_cache
from operator import itemgetter

X = list(map(int,readline().split()))
Y = list(map(int,readline().split()))

for i in [1,3,5]:
    X[i] += 1
    Y[i] += 1

X1 = X[:2]; X2 = X[2:4]; X3 = X[4:]
Y1 = Y[:2]; Y2 = Y[2:4]; Y3 = Y[4:]

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

U = 2 * 10 ** 6 + 10
MOD = 10**9 + 7
fact, fact_inv = make_fact(U,MOD)

@lru_cache(8)
def make_comb(n):
    return fact[n] * fact_inv[:n+1] % MOD * fact_inv[:n+1][::-1] % MOD

answer = 0
tasks = []
for p in itertools.product([0,1],repeat=6):
    x1,x2,x3,y1,y2,y3 = [A[i] for A,i in zip([X1,X2,X3,Y1,Y2,Y3],p)]
    sgn = (-1) ** sum(p)
    a,b,c,d = x2-x1, x3-x2, x2-x1+y2-y1, x3-x2+y3-y2
    c += 2; d += 2; sgn = -sgn
    tasks.append((a,b,c,d,sgn))

tasks.sort(key = itemgetter(2))

for a,b,c,d,sgn in tasks:
    
    
    D = a + b + 2
    
    L = max(0, D-d)
    R = min(c, D)
    if L > R:
        continue
    x = make_comb(c)[L:R+1]
    L,R = D-R,D-L
    y = make_comb(d)[L:R+1]
    x = x * y[::-1] % MOD
    
    np.cumsum(x,out=x)
    x %= MOD
    np.cumsum(x,out=x)
    x %= MOD
    L,R = D-R,D-L
    if 0 <= a-L < len(x):
        answer += sgn * x[a-L]

answer %= MOD
print(answer)

Verdicts: Wrong Answer

Wrong Answer

Accepted