Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N = int(input())
X = input()
MOD = 998244353

ans = 0
memo = dict()

# def get_divisor(n):
#     '''nの約数を返す
#     '''
#     d = set()
#     for i in range(1, int(n**0.5)+1):
#         if n % i == 0:
#             d.add(i)
#             d.add(n//i)
#     return d

def get_oddivisor(n):
    '''nの約数のうち商が奇数のものを返す
    '''
    d = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i%2 == 1:
                d.add(n//i)
            if (n//i)%2 == 1:
                d.add(i)
    return d

D = list(get_oddivisor(N))
D.sort()

def alternate(x, n):
    '''x: 00101, y: 11010, z: (00101)(11010)... n times
    '''
    y = ('0'*len(x) + bin(int(x,2) ^ (2**len(x)-1))[2:])[-len(x):]
    z = (x + y) * (n//2)
    if n%2 == 1:
        z += x
    return z

for d in D:
    cnt = int(X[:d], 2)
    if int(X, 2) >= int(alternate(X[:d], N//d), 2):
        cnt += 1
    dd = list(get_oddivisor(d))
    for ddd in dd:
        if ddd != d:
            cnt -= memo[ddd]
    memo[d] = cnt
    ans += cnt * 2 * d
    ans %= 998244353

print(ans)


### FIXED CODE ###

N = int(input())
X = input()
MOD = 998244353

ans = 0
memo = dict()

# def get_divisor(n):
#     '''nの約数を返す
#     '''
#     d = set()
#     for i in range(1, int(n**0.5)+1):
#         if n % i == 0:
#             d.add(i)
#             d.add(n//i)
#     return d

def get_oddivisor(n):
    '''nの約数のうち商が奇数のものを返す
    '''
    d = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i%2 == 1:
                d.add(n//i)
            if (n//i)%2 == 1:
                d.add(i)
    return d

D = list(get_oddivisor(N))
D.sort()

def alternate(x, n):
    '''x: 00101, y: 11010, z: (00101)(11010)... n times
    '''
    y = ('0'*len(x) + bin(int(x,2) ^ (2**len(x)-1))[2:])[-len(x):]
    z = (x + y) * (n//2)
    if n%2 == 1:
        z += x
    return z

for d in D:
    cnt = int(X[:d], 2)
    if int(X, 2) >= int(alternate(X[:d], N//d), 2):
        cnt += 1
    dd = list(get_oddivisor(d))
    for ddd in dd:
        if ddd != d:
            cnt -= memo[ddd]
    memo[d] = cnt
    ans += cnt * 2 * d
    ans %= 998244353

print(ans)
### BUGGY CODE ###

from collections import*
INF=10**18
h,w=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
s=[input() for _ in range(h)]
q=deque([(sh-1,sw-1)])
d=[[INF]*w for _ in range(h)]
d[sh-1][sw-1]=0
dx=[1,0,-1,0]
dy=[0,-1,0,1]
wx=[-2,-1,0,1,2]
wy=[-2,-1,0,1,2]
while q:
  x,y=q.popleft()
  for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]
    if not(0<=nx<h and 0<=ny<w):continue
    if s[nx][ny]=='.' and d[nx][ny]!=d[x][y]:
      d[nx][ny]=d[x][y]
      q.append((nx,ny))
  for i in range(5):
    for j in range(5):
      nx=x+wx[i]
      ny=y+wy[j]
      if not(0<=nx<h and 0<=ny<w):continue
      if s[nx][ny]=='.' and d[nx][ny]>d[x][y]:
        d[nx][ny]=d[x][y]+1
        q.append((nx,ny))
print(d[gh-1][gw-1] if d[gh-1][gw-1]!=INF else -1)

### FIXED CODE ###

from collections import*
INF=10**18
h,w=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
s=[input() for _ in range(h)]
q=deque([(sh-1,sw-1,0)])
d=[[INF]*w for _ in range(h)]
dx=[1,0,-1,0]
dy=[0,-1,0,1]
wx=[-2,-1,0,1,2]
wy=[-2,-1,0,1,2]
while q:
  x,y,c=q.popleft()
  if d[x][y]!=INF:continue
  d[x][y]=c
  for i,j in zip(dx,dy):
    nx=x+i
    ny=y+j
    if not(0<=nx<h and 0<=ny<w):continue
    if s[nx][ny]=='.' and d[nx][ny]==INF:
      q.appendleft((nx,ny,c))
  for i in wx:
    nx=x+i
    if not(0<=nx<h):continue
    for j in wy:
      ny=y+j
      if not(0<=ny<w):continue
      if s[nx][ny]=='.' and d[nx][ny]==INF:
        q.append((nx,ny,c+1))
print(d[gh-1][gw-1]if d[gh-1][gw-1]!=INF else -1)
### BUGGY CODE ###

k = int(input())

qu = list(range(1,10))

cnt = 0
while( cnt < k ):
  out = qu.pop(0)
  r = out%10
  if( r != 0 ):
    qu.append(10*out+r-1)
  qu.append(10*out+r)
  
  if( r!=9):
    qu.append(10*out+r+1)
  cnt+=1
    
print(out)

### FIXED CODE ###

k = int(input())
 
qu = list(range(1,10))
 
if (k <= 9):
  print(k)
else:
  cnt = 9
  while( cnt < k ):
    out = qu.pop(0)
    r = out%10
    y = 10*out+r
    if( r != 0 ):
      qu.append(y-1)
      cnt += 1
      if( cnt == k ):
        out = y-1
        break
    qu.append(y)
    cnt += 1
    if( cnt == k ):
      out = y
      break

    
    if( r!=9):
      qu.append(y+1)
      cnt+=1
      if( cnt == k ):
        out = y+1
        break
      

  print(out)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
import math
def ggcd(a):
    if len(a)==0:
        return 0
    i=0
    return math.gcd(a[i],ggcd(a[i+1:]))
n,x=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(n-1):
    b.append(abs(a[i]-a[i+1]))
c=ggcd(b)
d=abs(x-a[0])
print(math.gcd(c,d))

### FIXED CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
b=[]
if n==1 and x==a[0]:
    print(max(x,10**9-x))
    exit()
for i in range(n):
    b.append(abs(a[i]-x))
import math
c=0
for i in range(n):
    c=math.gcd(c,b[i])
    if c==1:
        break
print(c)
### BUGGY CODE ###

n, m = map(int, input().split())

a_list = []
tmp_start = []
tmp_goal = []
for i in range(m):
    a, b = map(int, input().split())
    
    # 島1から出ている船の行き先
    if a == 1:
        tmp_start.append(b)
    
    if b == n:
        tmp_goal.append(a)
    

    # 島1から意外の運航便のリスト
    #else:
    #    a_list.append([a, b])


for j in tmp_start:
    if j in tmp_goal:
        print('POSSIBLE')
        break

else:
    print('IMPOSSIBLE')

### FIXED CODE ###

n, m = map(int, input().split())

a_list = []
tmp_start = []
tmp_goal = []
for i in range(m):
    a, b = map(int, input().split())
    
    # 島1から出ている船の行き先
    if a == 1:
        tmp_start.append(b)
    
    if b == n:
        tmp_goal.append(a)
    

    # 島1から意外の運航便のリスト
    #else:
    #    a_list.append([a, b])

agree = set(tmp_start) & set(tmp_goal)

if len(agree) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

#for j in tmp_start:
#    if j in tmp_goal:
#        print('POSSIBLE')
#        break

#else:
#    print('IMPOSSIBLE')
### BUGGY CODE ###

A, B = map(int, input().split())
a = set()
b = set()
i = 2
while i <= 10 ** 9:
  if A <= 1:
    break
  while A % i == 0:
    a.add(i)
    A //= i
  i += 1
i = 2
while i <= 10 ** 9:
  if B <= 1:
    break
  while B % i == 0:
    b.add(i)
    B //= i
  i += 1
inter = a.intersection(b)
print(len(inter) + 1)

### FIXED CODE ###

A, B = map(int, input().split())
a = set()
b = set()
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
"""
i = 2
temp = A + 0
while i * i <= temp:
  if A <= 1:
    break
  while A % i == 0:
    a.add(i)
    A //= i
  i += 1
i = 2
temp = B + 0
while i * i <= temp:
  if B <= 1:
    break
  while B % i == 0:
    b.add(i)
    B //= i
  i += 1
"""
a = set([i[0] for i in factorization(A)])
b = set([i[0] for i in factorization(B)])
inter = a.intersection(b)
if A == 1 and B == 1:
  print(1)
else:
  print(len(inter) + 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

mod = 10 ** 9 + 7
ans = 0

for i in range(60):
    x = 0
    for j in range(N):
        if (A[j] >> i) & 1:
            x += 1
    buff = x * (N - x) % mod
    for j in range(i):
        buff = buff * 2 % mod
    ans += buff
    ans %= mod

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

mod = 10 ** 9 + 7
ans = 0
ni = 1

for i in range(60):
    x = sum([1 for j in range(N) if (A[j] >> i) & 1])
    buff = x * (N - x) * ni
    ans += buff
    ni = ni * 2

print(ans % mod)
### BUGGY CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    mask = (weights <= L)     
    return np.amax(dp_[L - weights[mask]] + values[mask])

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

import heapq

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

c = 1
hh = 0
X = []
for i in range(N):
	ac = A[i]
	for j in range(M):
		if ac != B[j]:
			heapq.heappush(X, min(A[i], B[j]))
			hh += 1

a = A[0]
for i in range(N - 1):
	if A[i + 1] == a:
		c = 0
		break
	a = A[i + 1]

b = B[0]
for i in range(M - 1):
	if B[i + 1] == b:
		c = 0
		break
	b = B[i + 1]

AA = []
BB = []
CC = []

for i in range(N):
	if A[i] in B:
		CC.append(A[i])
		B.remove(A[i])
	else:
		AA.append(A[i])

BB = B

xB = sorted(BB + CC)
xA = sorted(AA + CC)

for i in range(len(AA)):
	cc = 0
	for j in range(len(xB)):
		if xB[-1 - j] <= AA[i]:
			break
		else:
			cc += 1
	c = c * cc

for i in range(len(BB)):
	cc = 0
	for j in range(len(xA)):
		if xA[-1 - j] <= BB[i]:
			break
		else:
			cc += 1
	c = (c * cc) % 1000000007

if c != 0:
	if X != []:
		x = 0
	m = 0
	cnt = 0
	for i in range(hh):
		zzz = heapq.heappop(X)
		j = "G"
		if AA != []:
			if zzz == AA[0]:
				AA.remove(zzz)
				j = "N"
		if BB != []:
			if zzz == BB[0]:
				BB.remove(zzz)
				j = "N"

		if j == "G":
			if zzz != x:
				m += 1
			c = (c * (zzz - cnt - m)) % 1000000007
			cnt += 1
			x = zzz

print(c)

### FIXED CODE ###

import heapq
from collections import defaultdict

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

D = defaultdict(int)
c = 1
hh = 0
for i in range(N):
	for j in range(M):
		if A[i] != B[j]:
			d = min(A[i], B[j])
			D[d] += 1
			hh += 1

ds = sorted(D.items())
X = []
for i in range(len(ds)):
	X += [ds[i][0]] * ds[i][1]


a = A[0]
for i in range(N - 1):
	if A[i + 1] == a:
		c = 0
		break
	a = A[i + 1]

b = B[0]
for i in range(M - 1):
	if B[i + 1] == b:
		c = 0
		break
	b = B[i + 1]

AA = []
BB = []
CC = []

for i in range(N):
	if A[i] in B:
		CC.append(A[i])
		B.remove(A[i])
	else:
		AA.append(A[i])

BB = B

xB = sorted(BB + CC)
xA = sorted(AA + CC)

for i in range(len(AA)):
	cc = 0
	for j in range(len(xB)):
		if xB[-1 - j] <= AA[i]:
			break
		else:
			cc += 1
	c = c * cc

for i in range(len(BB)):
	cc = 0
	for j in range(len(xA)):
		if xA[-1 - j] <= BB[i]:
			break
		else:
			cc += 1
	c = (c * cc) % 1000000007

if c != 0:
	if X != []:
		x = 0
	m = 0
	cnt = 0
	for i in range(hh):
		zzz = X[i]
		j = "G"
		if AA != []:
			if zzz == AA[0]:
				AA.remove(zzz)
				j = "N"
		if BB != []:
			if zzz == BB[0]:
				BB.remove(zzz)
				j = "N"

		if j == "G":
			if zzz != x:
				m += 1
			c = (c * (zzz - cnt - m)) % 1000000007
			cnt += 1
			x = zzz

print(c)
### BUGGY CODE ###

N = int(input())
lst = ["3", "5", "7"]
ans = 0
while lst:
    a = lst.pop(0)
    if int(a) <= N:
        for c in ["3", "5", "7"]:
            lst.append(a + c)
        if all(a.count(c) > 0 for c in ["3", "5", "7"]):
            ans += 1
            
print(ans)

### FIXED CODE ###

N = int(input())
lst = ["3", "5", "7"]
ans = 0
while lst:
    a = lst.pop(0)
    if int(a) <= N:
        for c in ["3", "5", "7"]:
            if int(a + c) <= N:
                lst.append(a + c)
        if all(a.count(c) > 0 for c in ["3", "5", "7"]):
            ans += 1
            
print(ans)
### BUGGY CODE ###

N = int(input())
X = list(map(int,input().split()))
MOD = 10 ** 9 + 7
goal = X[-1]
ans = goal - X[0]
x = 1
for i in range(1,N-1):
    tmp = goal - X[i]
    ans = ((ans * (i+1) % MOD) + ((x*tmp) % MOD)) % MOD
    x *= i+1 % MOD
    #print(tmp,ans,x)
print(ans)

### FIXED CODE ###

def main():
    N = int(input())
    X = list(map(int,input().split()))
    MOD = 10 ** 9 + 7
    goal = X[-1]
    ans = goal - X[0]
    fact = [1]
    fact_inv = [1]
    for i in range(10**5+5):
        new_fact = fact[-1]*(i+1)%MOD
        fact.append(new_fact)
    count = 1
    for i in range(1,N-1):
        count += 1
        tmp = goal - X[i]
        ans = ((ans * count) + ((fact[i] * tmp))) % MOD  
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N = int(input())
S = input()

# R: 0, G: 1, B: 2

# 後ろにいくつ自分と同じ文字があるかの表を作る
DP = []
for i in range(3):
    DP.append([0] * N)

# 末尾だけループの前に代入
if S[-1] == 'R':
    DP[0][-1] = 1
elif S[-1] == 'G':
    DP[1][-1] = 1
elif S[-1] == 'B':
    DP[2][-1] = 1

for i in reversed(range(0, N - 1)):
    if S[i] == 'R':
        DP[0][i] = DP[0][i + 1] + 1
        DP[1][i] = DP[1][i + 1]
        DP[2][i] = DP[2][i + 1]
    elif S[i] == 'G':
        DP[0][i] = DP[0][i + 1]
        DP[1][i] = DP[1][i + 1] + 1
        DP[2][i] = DP[2][i + 1]
    elif S[i] == 'B':
        DP[0][i] = DP[0][i + 1]
        DP[1][i] = DP[1][i + 1]
        DP[2][i] = DP[2][i + 1] + 1

#print(DP)

ans = 0
for i in range(0, N - 2):
    s1 = S[i]
    zero_flag = False
    for j in range(i + 1, N - 1):
        # この先3文字目が存在しないことが分かっていたらjをこれ以上進めても意味がない
        if zero_flag:
            break

        s2 = S[j]
        # i と j が一緒か確認
        if s1 == s2:
            # 一緒であればこの2文字目はスキップ
            continue
        else:
            #print('i: {}, j: {}'.format(i, j))
            # 一緒じゃなければ3文字目(s3)を探す
            ij = (S[i], S[j])
            s3 = 'B'
            int_s3 = 2
            if 'R' not in ij:
                s3 = 'R'
                int_s3 = 0
            elif 'G' not in ij:
                s3 = 'G'
                int_s3 = 1

            # 3文字目の後ろの文字数を取得
            s3_back = DP[int_s3][j + 1]
            #print('s3: {}, s3_back = {}'.format(s3, s3_back))

            # 0ならスキップ
            if s3_back == 0:
                zero_flag = True
                continue

            # j + (j - i)の場所に3文字目があれば文字数を1引く
            if j + (j - i) < N:
                if S[j + (j - i)] == s3:
                    s3_back -= 1
                    #print('kita')

            ans += s3_back

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input())
S = input()

# R, G, Bの数をカウント
R_count = 0
G_count = 0
B_count = 0
for s in list(S):
    if s == 'R':
        R_count += 1
    elif s == 'G':
        G_count += 1
    elif s == 'B':
        B_count += 1

# R, G, Bの全組み合わせ数を求める
ans = R_count * G_count * B_count

# 3文字が等間隔に存在する組み合わせがあれば引いていく
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k = j + (j - i)
        if k >= N:
            break
        if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            ans -= 1

print(ans)
### BUGGY CODE ###

n = input()
l = map(int, raw_input().split())
ans = 1
for i in l:
    if (ans * i) <= 1e18:
        ans = ans * i
    else:
        ans = -1
print(ans) 

### FIXED CODE ###

n = input()
l = map(int, raw_input().split())
ans = 1
for i in l:
    if i == 0:
        ans = 0
if (ans != 0):
    for i in l:
        if (ans * i) <= 1e18:
            ans = ans * i
        else:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
QS = []

for _ in range(Q):
    l, r = map(int, input().split())
    print(S.count("AC", l - 1, r))
    # QS.append((l, r))
#
# for l, r in QS:
#     # print(S[l - 1:r])
#     print(S.count("AC", l - 1, r))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
QS = []

l = [0, 0]
last = S[0]
for i in range(1, len(S)):
    if last == 'A' and S[i] == 'C':
        l.append(l[-1] + 1)
    else:
        l.append(l[-1])
    last = S[i]

for _ in range(Q):
    left, right = map(int, input().split())
    QS.append((left, right))

# print(l)
for left, right in QS:
    ans = l[right] - l[left]
    print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
List = list(map(int, input().split()))

for i in range(K):
  Flag = False
  data = [0]*N
  ruiseki = [0]*N
  for i in range(N):
    first = i-List[i]
    last = i+List[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < N:
      data[last+1] +=-1
  List[0] = data[0]
  for i in range(N-1):
    List[i+1] = List[i] + data[i+1]
  if List.count(N) == N:
      Flag = True
  if Flag:
    break
print(*List)

### FIXED CODE ###

N,K=map(int,input().split())
List = list(map(int, input().split()))
 
def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki
 
for i in range(K):
  List = imosu(List,N)
  if List.count(N) == N:
    break
print(*List)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())

a = list(map(int, input().split()))
a.sort()
a = tuple(a)
cnt = 0

for i, ai in enumerate(a):
    if i != n-1 and ai == a[i+1]:
        cnt += 1
        continue
    for j, aj in enumerate(a[:i+1]):
        if i!=j and ai%aj==0:
            cnt += 1
            break

print(n-cnt)

### FIXED CODE ###

n = int(input())

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

c = [0] * (10**6+1)
for i in a:
    c[i] += 1

uni = []
a = list(set(a))

for i in a:
    if c[i] == 1:
        uni.append(i)

b = [0 for _ in range(10**6+1)]

for i in a:
    for j in range(i*2, 10**6+1, i):
        b[j] = 1

cnt = 0
for i in uni:
    if b[i] == 0:
        cnt += 1

print(cnt)
### BUGGY CODE ###

n,m = [int(s) for s in input().split(' ')]

ans = []
for i in range(m):
    l,r = [int(s) for s in input().split(' ')]
    temp = [i for i in range(l,r+1)]
    ans.append(set(temp))

anss = ans[0]
for j in range(1,len(ans)):
    anss &= ans[j]   
print(len(anss))

### FIXED CODE ###

n,m = [int(s) for s in input().split(' ')]

ans = []
minn = 10000000
maxx = 0
for i in range(m):
    l,r = [int(s) for s in input().split(' ')]
    maxx = max(maxx,l)
    minn = min(minn,r)
if minn - maxx < 0:
    print(0)
else:
    print(minn - maxx+1)
### BUGGY CODE ###

#d

n,m,k = map(int,input().split())

friend=[[] for _ in range(n)]
block=[[] for _ in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1) 

for i in range(k):
    a,b = map(int,input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)

from collections import deque
clusters=[]
visited=[0]*n
list_cluster=[0]*n
i_c=0
while sum(visited)<n:
    
    for i in range(n):
        if visited[i]==0:
            start=i
            break
    
    cluster =[start]
    q=deque([(start,togo) for togo in friend[start]]) #スタート地点から行ける場所を列挙
    visited[start]=1
    list_cluster[start]=i_c
    for togo in friend[start]:
        visited[togo]=1
        cluster.append(togo)
        list_cluster[togo]=i_c
    while q:
        parent,x = q.popleft()
    
        for y in friend[x]:
            if y == parent:#親ノードを飛ばし
                continue
            if visited[y]==0:
                q.append((x,y))#子ノードを追加
                visited[y]=1
                cluster.append(y)
                list_cluster[y]=i_c
#        print(parent,x,q)
    clusters.append(cluster)
    i_c+=1

ans=[]
for i in range(n):
    friend_cand = [j for j in range(n) if j in clusters[list_cluster[i]] ]
    #print(friend_cand)
    ans.append( len([ff for ff in friend_cand if ff not in block[i] and ff not in friend[i] ] ) -1)

print(*ans)

### FIXED CODE ###

#d

        
#     import sys
#     input = sys.stdin.readline

n,m,k = map(int,input().split())

friends_pair=[]
friend=[[] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    friends_pair.append((a,b))
    friend[a].append(b)
    friend[b].append(a) 
        
    
block=[]
for i in range(k):
    a,b = map(int,input().split())
    block.append((a-1,b-1))

from collections import deque
clusters=[]
visited=[0]*n
list_cluster=[0]*n
i_c=0
# while sum(visited)<n:
#     for i in range(n):
#         if visited[i]==0:
#             start=i
#             break
for i in range(n):
    if visited[i]==0:
        start=i
    else:
        continue

    cluster =[start]
    q=deque([(start,togo) for togo in friend[start]]) #スタート地点から行ける場所を列挙
    visited[start]=1
    list_cluster[start]=i_c
    for togo in friend[start]:
        visited[togo]=1
        cluster.append(togo)
        list_cluster[togo]=i_c
    while q:
        parent,x = q.popleft()
        for y in friend[x]:
            if y == parent:#親ノードを飛ばし
                continue
            if visited[y]==0:
                q.append((x,y))#子ノードを追加
                visited[y]=1
                cluster.append(y)
                list_cluster[y]=i_c
#        print(parent,x,q)
    clusters.append(cluster)
    i_c+=1

ans = [len(clusters[list_cluster[i]])-1 for i in range(n)  ]
for f0,f1 in friends_pair:
    if list_cluster[f0] ==  list_cluster[f1]:
        ans[f0]-=1
        ans[f1]-=1
for b0,b1 in block:
    if list_cluster[b0] ==  list_cluster[b1]:
        ans[b0]-=1
        ans[b1]-=1
print(*ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ken = [[] for _ in range(N)]
shi = []
for _ in range(M):
    P, Y = map(int, input().split())
    ken[P-1].append(Y)
    shi.append((P, Y))
for k in ken:
    k.sort()
for s in shi:
    print("{:06}{:06}".format(s[0], ken[s[0]-1].index(s[1])+1))

### FIXED CODE ###

from operator import itemgetter
N, M = map(int, input().split())
iPY = [0]*M
res = [0]*M
for i in range(M):
    P, Y = map(int, input().split())
    iPY[i] = (i, P, Y)
iPY.sort(key=itemgetter(2))
iPY.sort(key=itemgetter(1))
j = 1
p = iPY[0][1]
for i, P, Y in iPY:
    if P != p:
        j = 1
        p = P
    res[i] = "{:06}{:06}".format(P, j)
    j += 1
for s in res:
    print(s)
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for z in range(k+1):
    for y in range(k+1):
        for x in range(k+1):
            if s == y + x + z:
                count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for y in range(k+1):
    for x in range(k+1):
        z = s - x - y
        if 0 <= z <= k:
            count += 1
print(count)
### BUGGY CODE ###

n=int(input())
m=n
a=0
for i in range(len(str(n))):
    a+=m%10

    m=m//10

if a%9==0:
    print("Yes")

else:
    print("No")

### FIXED CODE ###

n=int(input())


if n%9==0:
    print("Yes")

else:
    print("No")