You are given a string $S$. Find the number of ways to choose an unordered pair of non-overlapping non-empty substrings of this string (let's denote them by $s_1$ and $s_2$ in such a way that $s_2$ starts after $s_1$ ends) such that their concatenation $s_1 + s_2$ is a palindrome.
Two pairs $(s_1, s_2)$ and $(s_1', s_2')$ are different if $s_1$ is chosen at a different position from $s_1'$ or $s_2$ is chosen at a different position from $s_2'$.

-----Input-----
The first and only line of the input contains a single string $S$.

-----Output-----
Print a single line containing one integer — the number of ways to choose a valid pair of substrings.

-----Constraints-----
- $1 \le |S| \le 1,000$
- $S$ contains only lowercase English letters

-----Subtasks-----
Subtask #1 (25 points): $|S| \le 100$
Subtask #2 (75 points): original constraints

-----Example Input-----
abba

-----Example Output-----
7

-----Explanation-----
The following pairs of substrings can be chosen: ("a", "a"), ("a", "ba"), ("a", "bba"), ("ab", "a"), ("ab", "ba"), ("abb", "a"), ("b", "b").

Difficulty: VERY_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
def palSub(s, n, isPal):
	for gap in range(n):
		for i in range(n - gap):
			j = i + gap
			if gap == 0:
				isPal[i][j] = 1
			elif gap == 1:
				isPal[i][j] = 1 if s[i] == s[j] else 0
			else:
				isPal[i][j] = 1 if s[i] == s[j] and isPal[i + 1][j - 1] else 0
	return isPal

def case1(n, isPal, c1):
	for i in range(n):
		for j in range(i, n):
			if i == j:
				c1[i][j] = 1
			else:
				c1[i][j] = c1[i][j - 1] + isPal[i][j]
	return c1

def case2(n, isPal, c2):
	for j in range(n - 1, -1, -1):
		for i in range(j, -1, -1):
			if i == j:
				c2[i][j] = 1
			else:
				c2[i][j] = c2[i + 1][j] + isPal[i][j]
	return c2

def getSub(s, n, c1, c2, res):
	for gap in range(n):
		for i in range(n - gap):
			j = i + gap
			if gap == 0:
				res[i][j] = 0
			elif gap == 1:
				res[i][j] = 1 if s[i] == s[j] else 0
			elif s[i] == s[j]:
				res[i][j] = 1 + c1[i + 1][j - 1] + c2[i + 1][j - 1] + res[i + 1][j - 1]
	return res

def __starting_point():
	s = input()
	n = len(s)
	isPal = [[0 for x in range(n)] for y in range(n)]
	isPal = palSub(s, n, isPal)
	c1 = [[-1 for x in range(n)] for y in range(n)]
	c2 = [[-1 for x in range(n)] for y in range(n)]
	c1 = case1(n, isPal, c1)
	c2 = case2(n, isPal, c2)
	res = [[0 for x in range(n)] for y in range(n)]
	res = getSub(s, n, c1, c2, res)
	mycount = 0
	for i in range(n):
		for j in range(n):
			mycount += res[i][j]
	print(mycount)
__starting_point()


def func(S):
	N = len(S)
	visit = [[None for _ in range(N)] for _ in range(N)]
	for i in range(N):
		visit[i][i] = True
	for i in range(N - 1):
		if S[i] == S[i + 1]:
			visit[i][i + 1] = True
		else:
			visit[i][i + 1] = False
	for k in range(3, N + 1):
		for i in range(0, N - k + 1):
			j = i + k - 1
			if S[i] == S[j] and visit[i + 1][j - 1] == True:
				visit[i][j] = True
			else:
				visit[i][j] = False
	x = [[0 for _ in range(N)] for _ in range(N)]
	for i in range(N):
		x[i][i] = 1
	for i in range(N - 1):
		if S[i] == S[i + 1]:
			x[i][i + 1] = 2
		else:
			x[i][i + 1] = 1
	for i in range(N - 2):
		for j in range(i + 2, N):
			if S[i] == S[j] and visit[i + 1][j - 1] == True:
				x[i][j] = x[i][j - 1] + 1
			else:
				x[i][j] = x[i][j - 1]
	y = [[0 for _ in range(N)] for _ in range(N)]
	for j in range(N):
		y[j][j] = 1
	for j in range(1, N):
		if S[j] == S[j - 1]:
			y[j - 1][j] = 2
		else:
			y[j - 1][j] = 1
	for j in range(2, N):
		for i in reversed(range(0, j - 1)):
			if S[i] == S[j] and visit[i + 1][j - 1] == True:
				y[i][j] = y[i + 1][j] + 1
			else:
				y[i][j] = y[i + 1][j]
	return (x, y)
S = input()
result = 0
N = len(S)
if N == 1:
	result = 0
elif N == 2:
	if S[0] == S[1]:
		result = 1
	else:
		result = 0
else:
	(x, y) = func(S)
	qw = [[[-1, -1] for _ in range(N)] for _ in range(N)]
	for i in range(N):
		qw[i][i][0] = 1
		qw[i][i][1] = 0
	for i in range(N - 1):
		if S[i] == S[i + 1]:
			qw[i][i + 1][0] = 1
			result += 1
		else:
			qw[i][i + 1][0] = 0
		qw[i][i + 1][1] = 0
	for z in range(3, N + 1):
		for i in range(0, N - z + 1):
			j = i + z - 1
			if S[i] != S[j]:
				qw[i][j][0] = 0
				qw[i][j][1] = 0
			else:
				if qw[i + 1][j - 1][0] == 0:
					qw[i][j][0] = 0
				else:
					qw[i][j][0] = j - i
				qw[i][j][1] = 1 + qw[i + 1][j - 1][1] + x[i + 1][j - 2] + y[i + 2][j - 1]
			result += qw[i][j][0] + qw[i][j][1]
print(result)


def get_the_num_of_palindromes_in_string_i_to_j_starting_at_i_and_ending_at_j(S):
	N = len(S)
	is_substring_palindrome = [[None for _ in range(N)] for _ in range(N)]
	for i in range(N):
		is_substring_palindrome[i][i] = True
	for i in range(N - 1):
		if S[i] == S[i + 1]:
			is_substring_palindrome[i][i + 1] = True
		else:
			is_substring_palindrome[i][i + 1] = False
	for k in range(3, N + 1):
		for i in range(0, N - k + 1):
			j = i + k - 1
			if S[i] == S[j] and is_substring_palindrome[i + 1][j - 1] == True:
				is_substring_palindrome[i][j] = True
			else:
				is_substring_palindrome[i][j] = False
	num_of_palindromic_substrings_in_string_i_to_j_starting_at_i = [[0 for _ in range(N)] for _ in range(N)]
	for i in range(N):
		num_of_palindromic_substrings_in_string_i_to_j_starting_at_i[i][i] = 1
	for i in range(N - 1):
		if S[i] == S[i + 1]:
			num_of_palindromic_substrings_in_string_i_to_j_starting_at_i[i][i + 1] = 2
		else:
			num_of_palindromic_substrings_in_string_i_to_j_starting_at_i[i][i + 1] = 1
	for i in range(N - 2):
		for j in range(i + 2, N):
			if S[i] == S[j] and is_substring_palindrome[i + 1][j - 1] == True:
				num_of_palindromic_substrings_in_string_i_to_j_starting_at_i[i][j] = num_of_palindromic_substrings_in_string_i_to_j_starting_at_i[i][j - 1] + 1
			else:
				num_of_palindromic_substrings_in_string_i_to_j_starting_at_i[i][j] = num_of_palindromic_substrings_in_string_i_to_j_starting_at_i[i][j - 1]
	num_of_palindromic_substrings_in_string_i_to_j_ending_at_j = [[0 for _ in range(N)] for _ in range(N)]
	for j in range(N):
		num_of_palindromic_substrings_in_string_i_to_j_ending_at_j[j][j] = 1
	for j in range(1, N):
		if S[j] == S[j - 1]:
			num_of_palindromic_substrings_in_string_i_to_j_ending_at_j[j - 1][j] = 2
		else:
			num_of_palindromic_substrings_in_string_i_to_j_ending_at_j[j - 1][j] = 1
	for j in range(2, N):
		for i in reversed(range(0, j - 1)):
			if S[i] == S[j] and is_substring_palindrome[i + 1][j - 1] == True:
				num_of_palindromic_substrings_in_string_i_to_j_ending_at_j[i][j] = num_of_palindromic_substrings_in_string_i_to_j_ending_at_j[i + 1][j] + 1
			else:
				num_of_palindromic_substrings_in_string_i_to_j_ending_at_j[i][j] = num_of_palindromic_substrings_in_string_i_to_j_ending_at_j[i + 1][j]
	return (num_of_palindromic_substrings_in_string_i_to_j_starting_at_i, num_of_palindromic_substrings_in_string_i_to_j_ending_at_j)
S = input()
N = len(S)
count = 0
if N == 1:
	count = 0
elif N == 2:
	if S[0] == S[1]:
		count = 1
	else:
		count = 0
else:
	(num_of_palindromic_substrings_in_string_i_to_j_starting_at_i, num_of_palindromic_substrings_in_string_i_to_j_ending_at_j) = get_the_num_of_palindromes_in_string_i_to_j_starting_at_i_and_ending_at_j(S)
	dp = [[[-1, -1] for _ in range(N)] for _ in range(N)]
	for i in range(N):
		dp[i][i][0] = 1
		dp[i][i][1] = 0
	for i in range(N - 1):
		if S[i] == S[i + 1]:
			dp[i][i + 1][0] = 1
			count += 1
		else:
			dp[i][i + 1][0] = 0
		dp[i][i + 1][1] = 0
	for k in range(3, N + 1):
		for i in range(0, N - k + 1):
			j = i + k - 1
			if S[i] != S[j]:
				dp[i][j][0] = 0
				dp[i][j][1] = 0
			else:
				if dp[i + 1][j - 1][0] == 0:
					dp[i][j][0] = 0
				else:
					dp[i][j][0] = j - i
				dp[i][j][1] = 1 + dp[i + 1][j - 1][1] + num_of_palindromic_substrings_in_string_i_to_j_starting_at_i[i + 1][j - 2] + num_of_palindromic_substrings_in_string_i_to_j_ending_at_j[i + 2][j - 1]
			count += dp[i][j][0] + dp[i][j][1]
print(count)


s = input()
N = len(s)
Nkj = [[0] * N for _ in range(N)]
for k in range(N):
	for j in range(N - 1, k, -1):
		if s[j] == s[k]:
			Nkj[k][j] = 1 + (Nkj[k - 1][j + 1] if k > 0 and j < N - 1 else 0)
		else:
			Nkj[k][j] = 0
		Nkj[j][k] = Nkj[k][j]
Pab = [[0] * N for _ in range(N)]
for m in range(N):
	for w in range(0, min(N - m, m + 1)):
		if s[m - w] == s[m + w]:
			Pab[m - w][m + w] = 1
			Pab[m + w][m - w] = 1
		else:
			break
	for w in range(0, min(N - m - 1, m + 1)):
		if s[m - w] == s[m + w + 1]:
			Pab[m - w][m + w + 1] = 1
			Pab[m + w + 1][m - w] = 1
		else:
			break
SPab = [list(Pab[a]) for a in range(N)]
for a in range(N):
	for b in range(a + 1, N):
		SPab[a][b] += SPab[a][b - 1]
	for b in range(a - 1, -1, -1):
		SPab[a][b] += SPab[a][b + 1]
C = 0
for i in range(-1, N - 1):
	for j in range(i + 1, N + 1):
		center_width = j - (i + 1)
		c = 0
		if center_width >= 2:
			if Pab[i + 1][j - 1]:
				c += center_width - 1
		if center_width >= 1:
			if i >= 0 and j < N:
				if center_width >= 2:
					Pi = SPab[i + 1][j - 2]
					Ni = Nkj[i][j]
					c += Pi * Ni
					Pj = SPab[j - 1][i + 2]
					Nj = Nkj[j][i]
					c += Pj * Nj
				c += Nkj[i][j]
			C += c
print(C)


def binarySearch(arr, l, r, x):
	mid = 0
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid + 1
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	if mid != len(arr):
		if arr[mid] < x:
			return mid + 1
	return mid
s = input()
strt = []
end = []
plc = []
landr = []
l2r = []
lr = []
ans = 0
n = len(s)
if n != 1:
	for i in range(n):
		strt.append([])
		end.append([])
		landr.append([0] * n)
		l2r.append([0] * n)
	for i in range(n):
		for j in range(n):
			if i - j < 0 or i + j >= n:
				break
			if s[i - j] == s[i + j]:
				if i - j - 1 >= 0:
					strt[i - j - 1].append(2 * j + 1)
				if i + j + 1 < n:
					end[i + j + 1].append(2 * j + 1)
			else:
				break
	for i in range(n):
		for j in range(n):
			if i - j < 0 or i + j + 1 >= n:
				break
			if s[i - j] == s[i + j + 1]:
				if i - j - 1 >= 0:
					strt[i - j - 1].append(2 * j + 2)
				if i + j + 2 < n:
					end[i + j + 2].append(2 * j + 2)
			else:
				break
	for i in range(n):
		end[i].sort()
		strt[i].sort()
	for i in range(n - 1):
		for j in range(i + 1, n):
			if s[i] == s[j]:
				lr.append([i, j])
				if i > 0 and j < n - 1:
					landr[i][j] = landr[i - 1][j + 1] + 1
				else:
					landr[i][j] = 1
	for i in lr:
		tempans = 1
		l = i[0]
		r = i[1]
		length = r - l - 1
		tempans += binarySearch(strt[l], 0, len(strt[l]) - 1, length)
		tempans += binarySearch(end[r], 0, len(end[r]) - 1, length)
		l2r[l][r] = tempans
	for i in range(n):
		for j in range(n):
			ans += l2r[i][j] * landr[i][j]
print(ans)


def oddPalindrome(task):
	answer = [0] * len(task)
	for i in range(len(task)):
		for k in range(min(len(task) - i, i + 1)):
			if task[i - k] != task[i + k]:
				break
			else:
				answer[i] += 1
	return answer

def evenPalindrome(task):
	answer = [0] * (len(task) - 1)
	for i in range(len(task) - 1):
		for k in range(min(i + 1, len(task) - 1 - i)):
			if task[i - k] != task[i + k + 1]:
				break
			else:
				answer[i] += 1
	return answer

def makeLeftPalindrome(oddPalindromes, evenPalindromes):
	n = len(oddPalindromes)
	leftPalindrome = [[0] * (n - x) for x in range(n)]
	for a in range(n):
		leftPalindrome[a][0] = 1
		for k in range(1, n - a):
			leftPalindrome[a][k] = leftPalindrome[a][k - 1] + (1 if k % 2 == 0 and oddPalindromes[a + k // 2] > k // 2 else 0) + (1 if k % 2 != 0 and evenPalindromes[a + k // 2] > k // 2 else 0)
	return leftPalindrome

def makeRightPalindrome(oddPalindromes, evenPalindromes):
	n = len(oddPalindromes)
	rightPalindrome = [[0] * (x + 1) for x in range(n - 1)]
	for b in range(n - 1):
		rightPalindrome[b][0] = 1
		for k in range(1, b + 1):
			rightPalindrome[b][k] = rightPalindrome[b][k - 1] + (1 if k % 2 == 0 and oddPalindromes[b - k // 2] > k // 2 else 0) + (1 if k % 2 != 0 and evenPalindromes[b - k // 2 - 1] > k // 2 else 0)
	return rightPalindrome

def makeSubstringPalindrome(leftPalindrome, rightPalindrome, task):
	n = len(leftPalindrome)
	answer = [[0] * n for _ in range(n)]
	for k in range(n - 1):
		for a in range(n - 1 - k):
			if task[a] == task[k + a + 1]:
				answer[a][k + a + 1] = (answer[a + 1][k + a] if k > 1 else 0) + (leftPalindrome[a + 1][k - 1] if k > 0 else 0) + (rightPalindrome[k + a][k - 1] if k > 0 else 0) + 1
	return answer
task = input()
oddP = oddPalindrome(task)
evenP = evenPalindrome(task)
leftP = makeLeftPalindrome(oddP, evenP)
rightP = makeRightPalindrome(oddP, evenP)
A = makeSubstringPalindrome(leftP, rightP, task)
print(sum([sum(x) for x in A]))


import sys, math
from sys import stdin, stdout
s = stdin.readline().strip()
ispalin = [[0 for i in range(len(s) + 1)] for i in range(len(s) + 1)]
suff = [[-1 for i in range(len(s) + 1)] for i in range(len(s) + 1)]
pref = [[-1 for i in range(len(s) + 1)] for i in range(len(s) + 1)]
lcp = [[0 for i in range(len(s) + 1)] for i in range(len(s) + 1)]
for i in range(0, len(s)):
	ispalin[i][i] = 1
	pref[i][i] = 1
	suff[i][i] = 1
	ispalin[i][i + 1] = 1
	pref[i][i + 1] = 2
	suff[i][i + 1] = 2
for l in range(2, len(s) + 1):
	for i in range(0, len(s) - l + 1):
		ispalin[i][i + l] = ispalin[i + 1][i + l - 1] * int(s[i] == s[i + l - 1])
		pref[i][i + l] = pref[i][i + l - 1] + ispalin[i][i + l]
		suff[i][i + l] = suff[i + 1][i + l] + ispalin[i][i + l]
for i in range(len(s)):
	for j in range(i + 1, len(s)):
		lcp[i][j] = (lcp[i - 1][j + 1] + 1) * int(s[i] == s[j])
ans = 0
for i in range(1, len(s)):
	for j in range(i, len(s)):
		ans += lcp[i - 1][j] * (suff[i][j] + pref[i][j] - 1)
stdout.write(str(ans))


DP = []
for i in range(1002):
	temp = []
	for j in range(1002):
		temp.append(False)
	DP.append(temp)

def Pre_process(s):
	n = len(s)
	for i in range(n):
		for j in range(n):
			DP[i][j] = False
	for j in range(1, n + 1):
		for i in range(0, n - j + 1):
			if j <= 2:
				if s[i] == s[i + j - 1]:
					DP[i][i + j - 1] = True
			elif s[i] == s[i + j - 1]:
				DP[i][i + j - 1] = DP[i + 1][i + j - 2]
	for i in range(0, n):
		for j in range(0, n):
			DP[j][i] = DP[i][j]

def main():
	s = input()
	Pre_process(s)
	n = len(s)
	left = []
	for i in range(n):
		temp = []
		for j in range(n):
			temp.append(0)
		left.append(temp)
	right = []
	for i in range(n):
		temp = []
		for j in range(n):
			temp.append(0)
		right.append(temp)
	for i in range(n):
		left[i][i] = 1
		for j in range(i + 1, n):
			left[i][j] = left[i][j - 1]
			if DP[i][j]:
				left[i][j] += 1
	for i in range(n - 1, -1, -1):
		right[i][i] = 1
		for j in range(i - 1, -1, -1):
			right[i][j] = right[i][j + 1]
			if DP[i][j]:
				right[i][j] += 1
	ans = []
	for i in range(n):
		temp = []
		for j in range(n):
			temp.append(0)
		ans.append(temp)
	for i in range(0, n - 1):
		if s[i] == s[i + 1]:
			ans[i][i + 1] = 1
	for j in range(2, n):
		for i in range(n - j):
			if s[i] == s[i + j]:
				ans[i][i + j] = ans[i + 1][i + j - 1] + 1 + left[i + 1][i + j - 1] + right[i + j - 1][i + 1]
	Sum = 0
	for i in range(n):
		for j in range(n):
			Sum += ans[i][j]
	print(Sum)
main()


s = str(input())
n = len(s)
DP = [[0] * n for _ in range(n)]
P = [[0] * n for _ in range(n)]
LR = [[0] * n for _ in range(n)]
RL = [[0] * n for _ in range(n)]
for i in range(n):
	for j in range(n):
		s2 = s[i:j + 1]
		if s[i:j + 1] == s2[::-1]:
			P[i][j] = 1
		if i > j:
			P[i][j] = 0
for i in range(n):
	for j in range(n):
		if j == 0:
			LR[i][j] = P[i][j]
		else:
			LR[i][j] = P[i][j] + LR[i][j - 1]
for j in range(n):
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			RL[i][j] = P[i][j]
		else:
			RL[i][j] = P[i][j] + RL[i + 1][j]
for j in range(n):
	for i in range(j, -1, -1):
		if i == j:
			DP[i][j] = 0
			continue
		if i > j:
			DP[i][j] = 0
			continue
		if s[i] == s[j]:
			DP[i][j] = 1 + RL[i + 1][j - 1] + LR[i + 1][j - 1] + DP[i + 1][j - 1]
		else:
			DP[i][j] = 0
s = 0
for i in range(n):
	s += sum(DP[i])
print(s)


from sys import *
import os
import re
from math import *
S = input()
N = len(S)
DPM2 = [0] * (N + 1)
DPM1 = [0] * (N + 1)
LM2 = [0] * (N + 1)
LM1 = [1] * (N + 1)
RM2 = [0] * (N + 1)
RM1 = [1] * (N + 1)
PM2 = [1] * (N + 1)
PM1 = [1] * (N + 1)
ans = 0
for le in range(2, N + 1):
	limit = N - le + 1
	DP = [0] * limit
	L = [0] * limit
	R = [0] * limit
	P = [0] * limit
	for i in range(0, limit):
		j = i + le - 1
		if S[i] == S[j]:
			DP[i] += DPM2[i + 1]
			DP[i] += 1
			DP[i] += LM2[i + 1]
			DP[i] += RM2[i + 1]
			P[i] = PM2[i + 1]
			ans += DP[i]
		L[i] = LM1[i] + P[i]
		R[i] = RM1[i + 1] + P[i]
	LM2 = LM1
	LM1 = L
	RM2 = RM1
	RM1 = R
	PM2 = PM1
	PM1 = P
	DPM2 = DPM1
	DPM1 = DP
print(ans)


st = str(input())

def checkpal(i, j, k, l):
	a = i
	b = l
	while a < b:
		if st[a] != st[b]:
			return -1
		if a == j:
			a = k - 1
		if b == k:
			b = j + 1
		a += 1
		b -= 1
	return 1
l = len(st)
count = 0
for i in range(l):
	for j in range(i, l):
		for k in range(j + 1, l):
			for m in range(k, l):
				if checkpal(i, j, k, m) == 1:
					count += 1
print(count)


s = input()
n = len(s)
palindromic = [[False for i in range(n)] for y in range(n)]
start = [[0 for i in range(n)] for y in range(n)]
end = [[0 for i in range(n)] for y in range(n)]
for i in range(n):
	for j in range(i + 1):
		if i == j:
			palindromic[j][i] = True
		elif s[j] == s[i] and j == i - 1:
			palindromic[j][i] = True
		elif palindromic[j + 1][i - 1] and s[j] == s[i]:
			palindromic[j][i] = True
for i in range(n):
	start[i][i] = 1
	for j in range(i + 1, n):
		if palindromic[i][j]:
			start[i][j] = start[i][j - 1] + 1
		else:
			start[i][j] = start[i][j - 1]
for i in range(n):
	end[i][i] = 1
	for j in range(i - 1, 0, -1):
		if palindromic[j][i]:
			end[j][i] = end[j + 1][i] + 1
		else:
			end[j][i] = end[j + 1][i]
cur = [0] * n
prev = [0] * n
for i in range(1, n):
	cur[i] = cur[i - 1]
	for j in range(i):
		if s[i] == s[j]:
			prev[j] = start[j + 1][i - 1] + end[j + 1][i - 1] + prev[j + 1] + 1
			cur[i] += prev[j]
		else:
			prev[j] = 0
print(cur[n - 1])


s = input()
n = len(s)
from bisect import bisect, bisect_left
from functools import lru_cache
memo = [[-1] * n for _ in range(n)]

def common(i, j):
	if i < 0 or j >= n or s[i] != s[j]:
		return 0
	if memo[i][j] != -1:
		return memo[i][j]
	memo[i][j] = 1 + common(i - 1, j + 1)
	return memo[i][j]
start = [[] for _ in range(n)]
end = [[] for _ in range(n)]
dp = set()
for i in range(n):
	dp.add((i, i))
	start[i].append(i)
	end[i].append(i)
for k in range(2, n + 1):
	for i in range(n - k + 1):
		j = i + k - 1
		if s[i] == s[j] and (k == 2 or (i + 1, j - 1) in dp):
			dp.add((i, j))
			start[i].append(j)
			end[j].append(i)
for i in range(n):
	end[i].reverse()
ans = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		if common(i, j):
			ans += common(i, j) * (bisect(start[i + 1], j - 1) + len(end[j - 1]) - bisect_left(end[j - 1], i + 1) + 1)
print(ans)