CodeEff/ECCO huggingface dataset:
# Original solution
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    a, b = il()
    t = [0] * 1000
    t[0] = 1
    for n in range(2, 1000):
        t[n-1] = t[n-2] + n
    for n in range(1000):
        if t[n] - a == t[n+1] - b:
            print((t[n]-a))
            exit()


if __name__ == '__main__':
    main()


# Optimized solution
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    a, b = il()
    print(((b-a)*(b-a+1)//2 - b))


if __name__ == '__main__':
    main()
# Original solution
a,b = list(map(int, input().split()))
polls = []
for i in range(1,1000):
    polls.append(sum(list(range(1,1000))[:i]))

d = {}
for i in range(1, len(polls)):
    d[polls[i]-polls[i-1]] = [polls[i-1],polls[i]]

print((d[b-a][0] - a))


# Optimized solution
a,b = list(map(int, input().split()))
print(((b-a)*(b-a+1)//2 - b))
# Original solution
#Stone Monument
a,b = list(map(int, input().split()))
M = []
ans = []
for i in range(1,1000,1):
	n = 1/2*i*(i+1)
	M.append(n)
for i in range(0,999,1):
	n = int(i*(i+1)/2)
	for j in range(0,n,1):
		if (a + j == M[i]) and (b + j == M[i+1]):
			print(j)
			exit()


# Optimized solution
#Stone Monument
a,b = list(map(int, input().split()))
M = []
for i in range(1,1000,1):
	n = 1/2*i*(i+1)
	M.append(n)
n = b-a-1
print((int(M[n-1]-a)))
# Original solution
a,b = list(map(int,input().split()))
d = b-a
b_len = d*(d+1)//2
print((b_len - b))

# Optimized solution
a,b = list(map(int,input().split()))

s = 0
for n in range(1000):
    if b-a == n:
        print((s-a))
        break
    s += n
# Original solution
a, b = list(map(int, input().split()))
l = []
t = 0
i = 1
while i <= 999:
  t += i
  l.append(t)
  i += 1

def f():
  for i in range(1, 499500):
    for j in range(len(l)-1):
      if a + i == l[j] and b + i == l[j+1]:
        return i

print((f()))

# Optimized solution
a, b = list(map(int, input().split()))
diff = b - a
b_2 = (diff + 1) * diff // 2
print((b_2 - b))
# Original solution
a,b = list(map(int, input().split()))

t = [1,]
flag = 0

for i in range(1000):
    t.append((i+2)+ t[i])

for j in range(len(t)):
    for k in range(499500):
        if t[j] - k == a and t[j+1] - k == b:
            print(k)
            flag = 1
        if flag == 1:break
    if flag == 1: break

# Optimized solution
a,b = list(map(int, input().split()))

t = [1,]

for i in range(1000):
    t.append((i+2)+ t[i])

for j in range(len(t)):
    if t[j] - a == t[j+1] - b:
        print((t[j] - a))
        break
# Original solution
a,b = list(map(int,input().split( )))
ans = 0
ans2 = 0
i = 1
while a > ans:
    ans = ans + i
    i += 1
ans2 = ans + (i)
while True:
    if (ans-a) == (ans2-b):
        print((ans-a))
        break
    else:
        ans = ans-(i-1)
        ans2 = ans-i

# Optimized solution
a,b = list(map(int,input().split( )))
c = b-a
d = 0
i = 1
ans = 0

while c > i:
    d = d+i
    i += 1
ans = d-a
print(ans)
# Original solution
a, b = list(map(int, input().split()))
out = 0
for i in range(b-a):
    out += i+1
print((out-b))

# Optimized solution
a, b = list(map(int, input().split()))
num = b - a
print((((1+num)*num)//2 - b))
# Original solution
a,b=list(map(int,input().split()))
s=0
for i in range(b-a+1):
	s=s+i
print((s-b))

# Optimized solution
a,b=list(map(int,input().split()))
n=b-a
print((n*(n+1)//2-b))
# Original solution
# -*- coding: utf-8 -*-

a, b = list(map(int, input().split()))

def tower(i):
    h = 0
    for i in range(1, i+1):
        h += i
    return h

notFound = True
i = 0
while(notFound):
    i += 1
    for j in range(1,1000):
        if (tower(j)-i==a )and(tower(j+1)-i==b):
#            print("Found")
            notFound = False
print(i)


# Optimized solution
# -*- coding: utf-8 -*-

a, b = list(map(int, input().split()))

def tower(i):
    h = 0
    for i in range(1, i+1):
        h += i
    return h

delta = b - a

print((tower(delta) - b))
# Original solution
def anotherpair(x, y):                
    l = []
    c=1
    for i in range(x, y+1):
        if c==0:
            l.append([i, i-1])
        c=0
    return l
n, a, b = list(map(int, input().split()))
if n==1:
    if a==b:
            ans = 1
    else:
        ans = 0
else:
    if a>b:
        ans = 0
    else:
        ans = len(anotherpair((n-2)*a, (n-2)*b))+1
print(ans)

# Optimized solution
n, a, b = list(map(int, input().split()))
if n==1:
    if a==b:
            ans = 1
    else:
        ans = 0
else:
    if a>b:
        ans = 0
    else:
        ans = ((n-2)*b-(n-2)*a)+1
print(ans)
# Original solution
import sys
input = sys.stdin.readline
from collections import *

N, A, B = list(map(int, input().split()))

if A>B:
    print((0))
    exit()

if N==1 and A!=B:
    print((0))
    exit()
    
low = A+B+(N-2)*A
high = A+B+(N-2)*B
print((high-low+1))

# Optimized solution
import sys
input = sys.stdin.readline
from collections import *

N, A, B = list(map(int, input().split()))

if A>B:
    print((0))
    exit()
    
m = B+A*(N-1)
M = A+B*(N-1)
print((max(0, M-m+1)))
# Original solution
n, a, b = list(map(int, input().split()))
M = b*(n-1)+a
m = b+a*(n-1)
print((max(M-m+1, 0)))


# Optimized solution
n, a, b = list(map(int, input().split()))
m = a*(n-1)+b
M = a+(n-1)*b
ans = max(M-m+1, 0)
print(ans)
# Original solution
N, A, B = list(map(int, input().split()))

if N == 1:
    if A == B:
        ans = 1
    else:
        ans = 0
elif A > B:
        ans = 0
else:
    ans = (B - A) * (N - 2) + 1

print(ans)

# Optimized solution
N, A, B = list(map(int, input().split()))


ans = (N - 2) * B - (N - 2) * A + 1
ans = max(ans, 0)
print(ans)
# Original solution
import itertools
n,a,b = [int(x) for x in input().split()]

r = list(range(a,b+1))
tmp = []
ans = 0

if a == b:
    print((1))
elif n == 1:
    print((0))
else:
    for v in itertools.combinations_with_replacement(r, n-2):
        if not sum(v) in tmp:
            ans += 1
            tmp.append(sum(v))

    print(ans)

# Optimized solution
n,a,b = [int(x) for x in input().split()]

if a > b:
    print((0))
elif n == 1:
    if a != b:
        print((0))
    else:
        print((1))
else:
    print(((b-a)*(n-2)+1))
# Original solution
def main():
    N, A, B = (int(i) for i in input().split())
    if (N == 1 and A != B) or (B - A < 0):
        print((0))
    elif N == 1:
        print((1))
    elif N == 2:
        print((1))
    else:
        print(((N-2)*B - (N-2)*A + 1))


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    N, A, B = (int(i) for i in input().split())
    if (N == 1 and A != B) or (B - A < 0):
        print((0))
    elif N == 1:
        print((1))
    else:
        print(((N-2)*B - (N-2)*A + 1))


if __name__ == '__main__':
    main()
# Original solution
N,A,B = list(map(int,input().split()))
if A>B or (N==1 and A!=B): print((0))
elif A==B or N==2: print((1))
else:
    N-=2
    print((B*N-A*N+1))

# Optimized solution
N,A,B = list(map(int,input().split()))
if (N==1 and A!=B) or B-A<0:print((0))
else: print(((A-B)*(2-N)+1))
# Original solution
n, a, b = list(map(int, input().split()))
if a > b:
    print((0))
    exit()
elif a == b:
    print((1))
    exit()
elif n == 1 and b - a > 0:
    print((0))
    exit()
elif n == 2:
    print((1))
    exit()
else:
    mid_num = n - 2
    num_num = b - a + 1
    ans = 0
    for i in range(mid_num-1):
        ans += num_num-1
    ans += num_num
    print(ans)


# Optimized solution
n, a, b = list(map(int, input().split()))
if a > b:
    print((0))
    exit()
elif a == b:
    print((1))
    exit()
elif n == 1 and b - a > 0:
    print((0))
    exit()
elif n == 2:
    print((1))
    exit()
else:
    mid_num = n - 2
    num_num = b - a + 1
    ans = 0
    ans += (num_num-1) * (mid_num-1) + num_num
    print(ans)
# Original solution
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, a, b = list(map(int, input().split()))

    mi = a * (n - 1) + b
    ma = a + b * (n - 1)
    print((max(0, ma - mi + 1)))


if __name__ == '__main__':
    resolve()


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, a, b = list(map(int, input().split()))

    mi = a * (n - 1) + b
    ma = b * (n - 1) + a
    print((max(0, ma - mi + 1)))


if __name__ == '__main__':
    resolve()
# Original solution
N, A, B = list(map(int,input().split()))
min = 0
max = 0
for i in range(0, N - 1):
    min += A
    max += B
if (max + A) - (min + B) + 1 < 0:
    print("0")
else:
    print(((max + A) - (min + B) + 1))

# Optimized solution
N, A, B = list(map(int,input().split()))
min = A * (N - 1) + B
max = B * (N - 1) + A
if (max - min) + 1 < 0:
    print("0")
else:
    print(((max - min) + 1))
# Original solution
N, A, B = list(map(int,input().split()))
if N == 1:
    print((1 if A==B else 0))
else:
    if A > B:
        print((0))
    else:
        m = A*(N-1)+B
        M = B*(N-1)+A
        print((M-m+1))


# Optimized solution
N, A, B = list(map(int,input().split()))
if A > B:
    print((0))
    exit(0)
if N == 1:
    if A != B:
        print((0))
    else:
        print((1))
else:
    print(((N-1)*B+A-(N-1)*A-B+1))
# Original solution
n,a,b=list(map(int,input().split()))
if a>b:
  print((0))
elif n==1:
  if a==b:
    print((1))
  else:
    print((0))
else:
  print((b*(n-1)+a - a*(n-1) - b + 1))

# Optimized solution
n,a,b=list(map(int,input().split()))
print((max(0,(n-2)*(b-a)+1)))
# Original solution
n,a,b=list(map(int,input().split()))
print((max(0,(n-2)*(b-a)+1)))

# Optimized solution
n,a,b=list(map(int,input().split()))
n-=2;print((max(b*n-a*n+1,0)))
# Original solution
n, a, b = list(map(int, input().split()))
if n == 0 or b < a or (n == 1 and a != b):
    print((0))
elif n == 1 and a == b:
    print((1))
else:
    print((1+(b-a)*(n-2)))

# Optimized solution
n, a, b = list(map(int, input().split()))
print((max(1+(b-a)*(n-2),0)))
# Original solution
N,A,B = list(map(int,input().split()))
print((max((N-1)*B+A-(N-1)*A-B+1,0)))

# Optimized solution
N,A,B = list(map(int,input().split()))
if A>B:
    ans = 0
elif N==1 and A!=B:
    ans = 0
elif N==1 and A==B:
    ans = 1
else:
    ans = (N-2)*(B-A)+1
print(ans)
# Original solution
n,a,b=list(map(int, input().split()))
pot = b-a+1
if(b<a):
    print((0))
    exit()
if n==0:
    print((0))
elif n==1:
    if a==b:
        print((1))
    else:print((0))
elif n==2:
    if a==b:print((1))
    print((1))
else:
    k = n-2
    ans=0

    for i in range(k):
        ans+=pot
        pot-=1
    print(ans)


# Optimized solution
n,a,b=list(map(int, input().split()))
pot = b-a+1
if(b<a):
    print((0))
    exit()
if n==0:
    print((0))
elif n==1:
    if a==b:
        print((1))
    else:print((0))
elif n==2:
    if a==b:print((1))
    print((1))
else:
    k = n-1
    m = k*b
    high = m+a
    low = a*k + b
    print((high-low+1))
# Original solution
n,a,b=list(map(int,input().split()))
if a>b or n<2and a<b:
  print((0))
else:
  print(((n-2)*(b-a)+1))

# Optimized solution
n,a,b=list(map(int,input().split()));print((max((n-2)*(b-a)+1,0)))
# Original solution
N, A, B = list(map(int, input().split()))

if A > B:
  print((0))
elif A == B:
  print((1))
else:
  if N == 1:
    if A != B:
      print((0))
    else:
      print((1))
  else:
    print(((N - 2) * (B - A) + 1))

# Optimized solution
n, a, b = list(map(int, input().split()))
ans = max(0, b * (n - 1) + a - (b + a * (n - 1)) + 1)
print(ans)
# Original solution
n,a,b = list(map(int,input().split()))
if n == 1 and a == b:
    print((1))
elif (n == 1 and a != b) or a > b:
    print((0))
else:
    print(((n-1)*b+a-((n-1)*a+b)+1))

# Optimized solution
n,a,b = list(map(int, input().split()))
if n == 1 and a==b:
    print((1))
elif n == 1 or a > b:
    print((0))
else:
    print(((n-2)*(b-a)+1))
# Original solution
N, A, B = list(map(int, input().split()))

if N == 1:
    if A == B:
        print((1))
    else:
        print((0))
elif A > B:
    print((0))
else:
    c = 0
    for _ in range(N-2):
        c += (B-A)
    print((c+1))


# Optimized solution
N, A, B = list(map(int, input().split()))

if N == 1:
    if A == B:
        print((1))
    else:
        print((0))
elif A > B:
    print((0))
else:
    print(((B-A)*(N-2)+1))
# Original solution
def main():
    n, a, b = list(map(int, input().split()))
    if (n == 1 and a != b) or (b < a):
        print((0))
        exit()
    mini = a * (n - 1) + b
    maxi = a + b * (n - 1)
    print((maxi - mini + 1))


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    n, a, b = list(map(int, input().split()))
    print((0 if (n == 1 and a != b) or a > b else (b - a) * (n - 1) + a - b + 1))
    
if __name__ == '__main__':
    main()
# Original solution
def calc():
    n, a, b = list(map(int, input().split()))
    if a > b:
        return 0
    if n == 1 and a < b:
        return 0

    upper = a + b * (n - 1)
    lower = b + a * (n - 1)
    return upper - lower + 1


print((calc()))


# Optimized solution
N, A, B = list(map(int, input().split()))

high = (N - 1) * B + A
low = (N - 1) * A + B
ans = high - low + 1
ans = max(0, ans)

print(ans)
# Original solution
n, p = list(map(int, input().split()))
w, b = [], []
for _ in range(n):
    ww, bb = list(map(int, input().split()))
    w.append(ww)
    b.append(bb)

s = []
for ww, bb in zip(w, b):
    s.append((100 - p) * ww + p * bb)
s.sort(reverse=True)

score = -sum(b) * p

cnt = 0
while score < 0:
    score += s[cnt]
    cnt += 1
print(cnt)

# (100-p)*w-p*b>=0


# Optimized solution
n, p = list(map(int, input().split()))

e = [tuple(map(int, input().split())) for _ in range(n)]
# e = [(w,b), ...]

e2 = sorted(((100 - p) * w + p * b for w, b in e), reverse=True)

rest = p * sum(b for _, b in e)

cur = 0
while rest > 0 and cur < n:
    rest -= e2[cur]
    cur += 1
print(cur)
# Original solution
import sys

sys.setrecursionlimit(10**7)
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

S = [0] + LS2()
n = len(S)
mod = 10**9+7

a,c,d = [0]*(n+1),[0]*(n+1),[0]*(n+1)
for i in range(1,n):
    a[i] = a[i-1]
    c[i] = c[i-1]
    d[i] = d[i-1]
    if S[i] == 'A':
        a[i] += 1
    elif S[i] == 'C':
        c[i] += 1
    elif S[i] == '?':
        d[i] += 1

X = [1]
for _ in range(n):
    X.append((X[-1]*3) % mod)

ans = 0
for i in range(1,n):
    if S[i] == 'B':
        ans += a[i-1]*(c[n-1]-c[i])*X[max(d[n-1],0)]
        ans %= mod
        ans += a[i-1]*(d[n-1]-d[i])*X[max(d[n-1]-1,0)]
        ans %= mod
        ans += d[i-1]*(c[n-1]-c[i])*X[max(d[n-1]-1,0)]
        ans %= mod
        ans += d[i-1]*(d[n-1]-d[i])*X[max(d[n-1]-2,0)]
        ans %= mod
    elif S[i] == '?':
        ans += a[i-1]*(c[n-1]-c[i])*X[max(d[n-1]-1,0)]
        ans %= mod
        ans += a[i-1]*(d[n-1]-d[i])*X[max(d[n-1]-2,0)]
        ans %= mod
        ans += d[i-1]*(c[n-1]-c[i])*X[max(d[n-1]-2,0)]
        ans %= mod
        ans += d[i-1]*(d[n-1]-d[i])*X[max(d[n-1]-3,0)]
        ans %= mod

print(ans)


# Optimized solution
import sys

def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

S = [0] + LS2()
n = len(S)
mod = 10**9+7

a,c,d = [0]*n,[0]*n,[0]*n  # a[i],c[i],d[i] = S1~SiにあるA,C,?の個数
for i in range(1,n):
    a[i] = a[i-1]
    c[i] = c[i-1]
    d[i] = d[i-1]
    if S[i] == 'A':
        a[i] += 1
    elif S[i] == 'C':
        c[i] += 1
    elif S[i] == '?':
        d[i] += 1

X = [1]  # X[i] = 3**i
for _ in range(n):
    X.append((X[-1]*3) % mod)

hatena = d[n-1]  # Sにある?の個数

ans = 0
for i in range(1,n):
    if S[i] == 'B':
        ans += a[i-1]*(c[n-1]-c[i])*X[max(hatena,0)]
        ans %= mod
        ans += a[i-1]*(d[n-1]-d[i])*X[max(hatena-1,0)]
        ans %= mod
        ans += d[i-1]*(c[n-1]-c[i])*X[max(hatena-1,0)]
        ans %= mod
        ans += d[i-1]*(d[n-1]-d[i])*X[max(hatena-2,0)]
        ans %= mod
    elif S[i] == '?':
        ans += a[i-1]*(c[n-1]-c[i])*X[max(hatena-1,0)]
        ans %= mod
        ans += a[i-1]*(d[n-1]-d[i])*X[max(hatena-2,0)]
        ans %= mod
        ans += d[i-1]*(c[n-1]-c[i])*X[max(hatena-2,0)]
        ans %= mod
        ans += d[i-1]*(d[n-1]-d[i])*X[max(hatena-3,0)]
        ans %= mod

print(ans)
# Original solution
import sys
input = sys.stdin.readline

S = input().rstrip()
N = len(S)
mod = 10**9 + 7
cnt = 0
A = B = C = 0
for c in S:
    if c == 'A':
        A += 3**cnt
    if c == 'B':
        B += A
    if c == 'C':
        C += B
    if c == '?':
        C = C * 3 + B
        B = B * 3 + A
        A = A * 3 + pow(3, cnt, mod)
        cnt += 1
    A %= mod
    B %= mod
    C %= mod
print(C)

# Optimized solution
import sys
input = sys.stdin.readline

S = input().rstrip()
N = len(S)
mod = 10**9 + 7
cnt = 0
A = B = C = 0
for c in S:
    if c == 'A':
        A += pow(3, cnt, mod)
    if c == 'B':
        B += A
    if c == 'C':
        C += B
    if c == '?':
        C = C * 3 + B
        B = B * 3 + A
        A = A * 3 + pow(3, cnt, mod)
        cnt += 1
    A %= mod
    B %= mod
    C %= mod
print(C)
# Original solution
import sys
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 1
for c in S:
    if c == 'A':
        a += q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+q, ab*3+a, ans*3+ab, q*3
print((ans % mod))


# Optimized solution
import sys
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 1
for c in S:
    if c == 'A':
        a += q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+q, ab*3+a, ans*3+ab, q*3
    a %= mod
    ab %= mod
    ans %= mod
    q %= mod
print((ans % mod))
# Original solution
s=input()[-1::-1]
n=len(s)
dp=[[0,0,0,0] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for j in range(4):
        dp[i+1][j]=dp[i][j]%1000000007
    if s[i]=="?":
        dp[i+1][0]+=2*dp[i][0]
        for j in range(1,4):
            dp[i+1][j]+=2*dp[i][j]+dp[i][j-1]
    else:
        index=" CBA".find(s[i])
        dp[i+1][index]+=dp[i][index-1]
print((dp[n][3]%1000000007))

# Optimized solution
mod = 1000000007
s = input()[-1::-1] #入力のタイミングで文字列を反転してしまう
n = len(s)
dp = [[0]*4 for i in range(n+1)]
dp[0][0] = 1 #0文字から0文字選ぶ方法だけ1で初期化。他は0。
for i in range(n):
    for j in range(4):
        dp[i+1][j] = dp[i][j] % mod #とりあえず一つ前の値はコピー
    if s[i] == "?":
        dp[i+1][0] += (2*dp[i][0]) % mod #コピーしたものに2倍を足せば合計3倍。0だけは一項少ないので別扱い。
        for j in range(1, 4):
            dp[i+1][j] += (2*dp[i][j]+dp[i][j-1]) % mod
    else:
        index = "CBA".find(s[i])+1 #indexを1-originにするために1を加えている
        dp[i+1][index] += dp[i][index-1] % mod
print((dp[n][3] % mod))
# Original solution
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# DP[0, 0], Aの数、ABの数、ABCの数
MOD = 10 ** 9 + 7
S = sr()
dp = [0, 0, 0]
total = 1
for s in S:
    if s == 'A':
        dp[0] += total
    elif s == 'B':
        dp[1] += dp[0]
    elif s == 'C':
        dp[2] += dp[1]
    elif s == '?':
        dp[2] = dp[2]*3 + dp[1]
        dp[1] = dp[1]*3 + dp[0]
        dp[0] = dp[0]*3 + total
        total *= 3
    #print(dp, total)

print((dp[2]%MOD))


# Optimized solution
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# DP[0, 0], Aの数、ABの数、ABCの数
MOD = 10 ** 9 + 7
S = sr()
dp = [0, 0, 0]
total = 1
for s in S:
    if s == 'A':
        dp[0] += total
    elif s == 'B':
        dp[1] += dp[0]
    elif s == 'C':
        dp[2] += dp[1]
    elif s == '?':
        dp[2] = dp[2]*3 + dp[1]
        dp[1] = dp[1]*3 + dp[0]
        dp[0] = dp[0]*3 + total
        total *= 3
    total %= MOD; dp[0] %= MOD; dp[1] %= MOD; dp[2] %= MOD
    #print(dp, total)

answer = dp[2] % MOD
print(answer)
# Original solution
S=input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M


print(abc%M)


# Optimized solution
S=input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print(abc%M)
# Original solution
S=input()
N=len(S)
mod=10**9+7

num=[ [ 0 for i in range(4) ] for j in range(N) ]		# i=0 A, i=1 B, i=2 C, i=3 ?

for i in range(N):
	if i==0:
		if S[i]=="A":  num[i][0]=1
		elif S[i]=="B":  num[i][1]=1		
		elif S[i]=="C":  num[i][2]=1
		elif S[i]=="?":  num[i][3]=1
	else:
		for j in range(4):
			num[i][j]=num[i-1][j]
			
		if S[i]=="A":  num[i][0]+=1
		elif S[i]=="B":  num[i][1]+=1		
		elif S[i]=="C":  num[i][2]+=1
		elif S[i]=="?":  num[i][3]+=1		

ans=0

for i in range(1,N):
	if S[i]=="B" or S[i]=="?":
		a=num[i-1][0]
		c=num[N-1][2]-num[i][2]
		ql=num[i-1][3]
		qr=num[N-1][3]-num[i][3]

		#ABC
		ans+=a*(3**ql)*c*(3**qr)%mod

		#AB?
		if qr>0:
			ans+=a*qr*(3**ql)*(3**(qr-1) )%mod

		#?BC
		if ql>0:
			ans+=(3**(ql-1) )*ql*c*(3**qr)%mod

		#?B?
		if ql>0 and qr>0:
			ans+=ql*(3**(ql-1) )*qr*(3**(qr-1) )%mod

print(ans%mod)



# Optimized solution
S=input()
N=len(S)
mod=10**9+7

num=[ [ 0 for i in range(4) ] for j in range(N) ]		# i=0 A, i=1 B, i=2 C, i=3 ?

for i in range(N):
	if i==0:
		if S[i]=="A":  num[i][0]=1
		elif S[i]=="B":  num[i][1]=1		
		elif S[i]=="C":  num[i][2]=1
		elif S[i]=="?":  num[i][3]=1
	else:
		for j in range(4):
			num[i][j]=num[i-1][j]
			
		if S[i]=="A":  num[i][0]+=1
		elif S[i]=="B":  num[i][1]+=1		
		elif S[i]=="C":  num[i][2]+=1
		elif S[i]=="?":  num[i][3]+=1		

ans=0

for i in range(1,N):
	if S[i]=="B" or S[i]=="?":
		a=num[i-1][0]
		c=num[N-1][2]-num[i][2]
		ql=num[i-1][3]
		qr=num[N-1][3]-num[i][3]

		#ABC
		ans+=a*pow(3,ql,mod)*c*pow(3,qr,mod)

		#AB?
		if qr>0:
			ans+=a*pow(3,ql,mod)*pow(3,(qr-1),mod )*qr

		#?BC
		if ql>0:
			ans+=pow(3,(ql-1),mod )*ql*c*pow(3,qr,mod)

		#?B?
		if ql>0 and qr>0:
			ans+=pow(3,(ql-1),mod )*ql*pow(3,(qr-1),mod )*qr

print(ans%mod)
# Original solution
import sys
S=sys.stdin.readline()

mod=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	elif x=="B":
		ab+=a
	elif x=="C":
		ans+=ab
	elif x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print(ans%mod)


# Optimized solution
S=input()
 
M=10**9+7
 
all=1
abc=0
ab=0
a=0
 
for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab
 
	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3
 
	abc%=M
	ab%=M
	a%=M
	all%=M
 
 
print(abc%M)