Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    xy.append([int(item) for item in input().split()])
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i, x=1):
    while i <= n:
        cnt[i] += x
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow2 = []
a = 1
for i in range(n+1):
    pow2.append(a)
    a *= 2
    a %= MOD

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow2[points_in_quad[0][i]]
    free2 = pow2[points_in_quad[1][i]]
    free3 = pow2[points_in_quad[2][i]]
    free4 = pow2[points_in_quad[3][i]]
    ans -= (((free2 - 1) * (free4 - 1)) % MOD) * (((free1 - 1) * (free3 - 1)) % MOD) % MOD
    ans += ((free1 * free3) % MOD) * (((free2 - 1) * (free4 - 1)) % MOD) % MOD
    ans += ((free2 * free4) % MOD) * ((free1 - 1) * (free3 - 1) % MOD) % MOD
    ans %= MOD
# target included, n >= 2 selected
ans += pow2[n-1] * n % MOD
print(ans % MOD)

Fixed submission:
import sys
input = sys.stdin.readline

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    x, y = [int(item) for item in input().split()]
    xy.append((x, y))
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i):
    while i <= n:
        cnt[i] += 1
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow2 = []
a = 1
for i in range(n+1):
    pow2.append(a)
    a *= 2
    a %= MOD

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow2[points_in_quad[0][i]]
    free2 = pow2[points_in_quad[1][i]]
    free3 = pow2[points_in_quad[2][i]]
    free4 = pow2[points_in_quad[3][i]]
    fix24 = (free2 - 1) * (free4 - 1) % MOD
    fix13 = (free1 - 1) * (free3 - 1) % MOD
    ans -= fix24 * fix13 % MOD
    ans += ((free1 * free3) % MOD) * fix24 % MOD
    ans += ((free2 * free4) % MOD) * fix13 % MOD
    ans %= MOD
# target included, n >= 2 selected
ans += pow2[n-1] * n % MOD
print(ans % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    xy.append([int(item) for item in input().split()])
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i, x=1):
    while i <= n:
        cnt[i] += x
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow2 = []
a = 1
for i in range(n+1):
    pow2.append(a)
    a *= 2
    a %= MOD

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow2[points_in_quad[0][i]]
    free2 = pow2[points_in_quad[1][i]]
    free3 = pow2[points_in_quad[2][i]]
    free4 = pow2[points_in_quad[3][i]]
    ans -= (((free2 - 1) * (free4 - 1)) % MOD) * (((free1 - 1) * (free3 - 1)) % MOD) % MOD
    ans += ((free1 * free3) % MOD) * (((free2 - 1) * (free4 - 1)) % MOD) % MOD
    ans += ((free2 * free4) % MOD) * ((free1 - 1) * (free3 - 1) % MOD) % MOD
    ans %= MOD
    # target included, n >= 2 selected
    ans += pow(2, n-1, MOD)
    ans %= MOD
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    x, y = [int(item) for item in input().split()]
    xy.append((x, y))
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i):
    while i <= n:
        cnt[i] += 1
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow2 = []
a = 1
for i in range(n+1):
    pow2.append(a)
    a *= 2
    a %= MOD

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow2[points_in_quad[0][i]]
    free2 = pow2[points_in_quad[1][i]]
    free3 = pow2[points_in_quad[2][i]]
    free4 = pow2[points_in_quad[3][i]]
    fix24 = (free2 - 1) * (free4 - 1) % MOD
    fix13 = (free1 - 1) * (free3 - 1) % MOD
    ans -= fix24 * fix13 % MOD
    ans += ((free1 * free3) % MOD) * fix24 % MOD
    ans += ((free2 * free4) % MOD) * fix13 % MOD
    ans %= MOD
# target included, n >= 2 selected
ans += pow2[n-1] * n % MOD
print(ans % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    xy.append([int(item) for item in input().split()])
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i, x=1):
    while i <= n:
        cnt[i] += x
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow_dict = dict()
for i in range(n):
    pow_dict[i] = pow(2, i, MOD)
ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow_dict[points_in_quad[0][i]]
    free2 = pow_dict[points_in_quad[1][i]]
    free3 = pow_dict[points_in_quad[2][i]]
    free4 = pow_dict[points_in_quad[3][i]]
    ans -= (((free2 - 1) * (free4 - 1)) % MOD) * (((free1 - 1) * (free3 - 1)) % MOD) % MOD
    ans += ((free1 * free3) % MOD) * (((free2 - 1) * (free4 - 1)) % MOD) % MOD
    ans += ((free2 * free4) % MOD) * ((free1 - 1) * (free3 - 1) % MOD) % MOD
    ans %= MOD
    # target included, n >= 2 selected
    ans += pow(2, n-1, MOD)
    ans %= MOD
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    x, y = [int(item) for item in input().split()]
    xy.append((x, y))
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i):
    while i <= n:
        cnt[i] += 1
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow2 = []
a = 1
for i in range(n+1):
    pow2.append(a)
    a *= 2
    a %= MOD

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow2[points_in_quad[0][i]]
    free2 = pow2[points_in_quad[1][i]]
    free3 = pow2[points_in_quad[2][i]]
    free4 = pow2[points_in_quad[3][i]]
    fix24 = (free2 - 1) * (free4 - 1) % MOD
    fix13 = (free1 - 1) * (free3 - 1) % MOD
    ans -= fix24 * fix13 % MOD
    ans += ((free1 * free3) % MOD) * fix24 % MOD
    ans += ((free2 * free4) % MOD) * fix13 % MOD
    ans %= MOD
# target included, n >= 2 selected
ans += pow2[n-1] * n % MOD
print(ans % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    xy.append([int(item) for item in input().split()])
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i, x=1):
    while i <= n:
        cnt[i] += x
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow_dict = dict()
for i in range(n):
    pow_dict[i] = pow(2, i, MOD)
ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow_dict[points_in_quad[0][i]]
    free2 = pow_dict[points_in_quad[1][i]]
    free3 = pow_dict[points_in_quad[2][i]]
    free4 = pow_dict[points_in_quad[3][i]]
    # free1 = pow(2, points_in_quad[0][i], MOD)
    # free2 = pow(2, points_in_quad[1][i], MOD)
    # free3 = pow(2, points_in_quad[2][i], MOD)
    # free4 = pow(2, points_in_quad[3][i], MOD)
    ans -= (((free2 - 1) * (free4 - 1)) % MOD) * (((free1 - 1) * (free3 - 1)) % MOD) % MOD
    ans += ((free1 * free3) % MOD) * (((free2 - 1) * (free4 - 1)) % MOD) % MOD
    ans += ((free2 * free4) % MOD) * ((free1 - 1) * (free3 - 1) % MOD) % MOD
    # target included, n >= 2 selected
    ans += pow(2, n-1, MOD)
    ans %= MOD
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    x, y = [int(item) for item in input().split()]
    xy.append((x, y))
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i):
    while i <= n:
        cnt[i] += 1
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow2 = []
a = 1
for i in range(n+1):
    pow2.append(a)
    a *= 2
    a %= MOD

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow2[points_in_quad[0][i]]
    free2 = pow2[points_in_quad[1][i]]
    free3 = pow2[points_in_quad[2][i]]
    free4 = pow2[points_in_quad[3][i]]
    fix24 = (free2 - 1) * (free4 - 1) % MOD
    fix13 = (free1 - 1) * (free3 - 1) % MOD
    ans -= fix24 * fix13 % MOD
    ans += ((free1 * free3) % MOD) * fix24 % MOD
    ans += ((free2 * free4) % MOD) * fix13 % MOD
    ans %= MOD
# target included, n >= 2 selected
ans += pow2[n-1] * n % MOD
print(ans % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    xy.append([int(item) for item in input().split()])
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i, x=1):
    while i <= n:
        cnt[i] += x
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow(2, points_in_quad[0][i], MOD)
    free2 = pow(2, points_in_quad[1][i], MOD)
    free3 = pow(2, points_in_quad[2][i], MOD)
    free4 = pow(2, points_in_quad[3][i], MOD)
    ans -= (((free2 - 1) * (free4 - 1)) % MOD) * (((free1 - 1) * (free3 - 1)) % MOD) % MOD
    ans += ((free1 * free3) % MOD) * (((free2 - 1) * (free4 - 1)) % MOD) % MOD
    ans += ((free2 * free4) % MOD) * ((free1 - 1) * (free3 - 1) % MOD) % MOD
    # target included, n >= 2 selected
    ans += pow(2, n-1, MOD)
    ans %= MOD
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    x, y = [int(item) for item in input().split()]
    xy.append((x, y))
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i):
    while i <= n:
        cnt[i] += 1
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow2 = []
a = 1
for i in range(n+1):
    pow2.append(a)
    a *= 2
    a %= MOD

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow2[points_in_quad[0][i]]
    free2 = pow2[points_in_quad[1][i]]
    free3 = pow2[points_in_quad[2][i]]
    free4 = pow2[points_in_quad[3][i]]
    fix24 = (free2 - 1) * (free4 - 1) % MOD
    fix13 = (free1 - 1) * (free3 - 1) % MOD
    ans -= fix24 * fix13 % MOD
    ans += ((free1 * free3) % MOD) * fix24 % MOD
    ans += ((free2 * free4) % MOD) * fix13 % MOD
    ans %= MOD
# target included, n >= 2 selected
ans += pow2[n-1] * n % MOD
print(ans % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    xy.append([int(item) for item in input().split()])
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i, x=1):
    while i <= n:
        cnt[i] += x
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow(2, points_in_quad[0][i], MOD)
    free2 = pow(2, points_in_quad[1][i], MOD)
    free3 = pow(2, points_in_quad[2][i], MOD)
    free4 = pow(2, points_in_quad[3][i], MOD)
    ans -= (free2 - 1) * (free4 - 1) * (free1 - 1) * (free3 - 1) % MOD
    ans += free1 * free3 * (free2 - 1) * (free4 - 1) % MOD
    ans += free2 * free4 * (free1 - 1) * (free3 - 1) % MOD
    # target included, n >= 2 selected
    ans += pow(2, n-1, MOD)
    ans %= MOD
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    x, y = [int(item) for item in input().split()]
    xy.append((x, y))
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i):
    while i <= n:
        cnt[i] += 1
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow2 = []
a = 1
for i in range(n+1):
    pow2.append(a)
    a *= 2
    a %= MOD

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow2[points_in_quad[0][i]]
    free2 = pow2[points_in_quad[1][i]]
    free3 = pow2[points_in_quad[2][i]]
    free4 = pow2[points_in_quad[3][i]]
    fix24 = (free2 - 1) * (free4 - 1) % MOD
    fix13 = (free1 - 1) * (free3 - 1) % MOD
    ans -= fix24 * fix13 % MOD
    ans += ((free1 * free3) % MOD) * fix24 % MOD
    ans += ((free2 * free4) % MOD) * fix13 % MOD
    ans %= MOD
# target included, n >= 2 selected
ans += pow2[n-1] * n % MOD
print(ans % MOD)