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

def main():
    n,a,b = map(int,input().split())
    MOD = (10**9)+7
    # s = powpow(2,n)
    s=pow(2,n,MOD) -1
    f,inv_f=comInit(MOD,n)

    s-=calCom(n,a,MOD,f,inv_f)
    s-=calCom(n,b,MOD,f,inv_f)

    print(s)

def powpow(a,n):
    mod = (10**9)+7
    x = 1
    i = 0
    while n > 0:
        print(bin(n))
        if bin(n & 1):
            x=x*a
            # x%=mod
        a*=a
        print(x)
        # a%=mod
        i+=1
        n=n>>1

    print('aaa')
    return x

def comInit(MOD, n):
    fact=[1,1] # fact[n]はnの階乗
    invr=[0,1] # invr[n]はnの逆元
    invr_fact=[1,1] # invr_fact[n]は逆元の階乗

    for i in range(2,n+1):
        fact.append(fact[-1]*i%MOD)
        invr.append(-invr[MOD%i]*(MOD//i)%MOD)
        invr_fact.append(invr_fact[-1]*invr[-1]%MOD)
    return fact,invr_fact

def calCom(n,k,MOD,fact,invr_fact):
    k=min(k,n-k)
    return fact[n]*invr_fact[k]*invr_fact[n-k]%MOD



if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    n,a,b = map(int,input().split())
    MOD = 10**9 +7
    s = pow(2,n,MOD)-1
    P_ni = 1
    F_i = 1


    for i in range(1,b + 1):
        P_ni=P_ni*(n-i+1)%MOD
        F_i=F_i* i % MOD
        if i == a or i == b:
            s-=P_ni*pow(F_i,MOD-2,MOD)



    print(s%MOD)

if __name__=='__main__':
    main()
### BUGGY CODE ###

import math
K=int(input())
sum=0

for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      ans=math.gcd(math.gcd(i,j),k)
      sum=sum+ans
      
print(sum)

### FIXED CODE ###

import math

K=int(input())
sum=0


for i in range(1,K+1):
    for j in range(1,K+1):
        a=math.gcd(i,j)
        for k in range(1,K+1):
            b=math.gcd(a, k)
            sum = sum + b

print(sum)
### BUGGY CODE ###

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

R,C,K = map(int, input().split())

items = [[0 for _ in range(C+1)] for _ in range(R+1)]
for i in range(K):
  r,c,v = map(int, input().split())
  items[r][c] = v

DP = [[[0,0,0,0] for _ in range(C+1)] for _ in range(R+1)]

for r in range(1,R+1):
  for c in range(1,C+1):
    DP0 = DP[r-1][c][3]
    DP1 = max(DP0+items[r][c],DP[r][c-1][1])
    DP2 = max(DP1,DP[r][c-1][2],DP[r][c-1][1]+items[r][c])
    DP3 = max(DP2,DP[r][c-1][3],DP[r][c-1][2]+items[r][c])
    DP[r][c][0] = DP0
    DP[r][c][1] = DP1
    DP[r][c][2] = DP2
    DP[r][c][3] = DP3
        
print(DP[R][C][3])

### FIXED CODE ###

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

R,C,K = map(int, input().split())

items = [[0 for _ in range(C+1)] for _ in range(R+1)]
for i in range(K):
  r,c,v = map(int, input().split())
  items[r][c] = v

DP_prev = [0 for _ in range(C+1)]

for r in range(1,R+1):
  DP = [[0 for _ in range(C+1)],[0 for _ in range(C+1)],[0 for _ in range(C+1)]]
  for c in range(1,C+1):
    item = items[r][c]
    DP1 = max(DP_prev[c]+item,DP[0][c-1])
    DP2 = max(DP1,DP[1][c-1],DP[0][c-1]+item)
    DP3 = max(DP2,DP[2][c-1],DP[1][c-1]+item)
    DP[0][c] = DP1
    DP[1][c] = DP2
    DP[2][c] = DP3
  DP_prev = DP[2]
        
print(DP_prev[C])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def lcs(x, y):
    n = len(x)
    m = len(y)
    dp = [0 for j in range(m + 1)]

    for i in range(1, n + 1):
        dp_prev = dp[:]
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[j] = dp_prev[j - 1] + 1
            elif dp_prev[j] < dp[j - 1]:
                dp[j] = dp[j - 1]
            else:
                dp[j] = dp_prev[j]

    return dp[m]


if __name__ == '__main__':
    import sys
    q = int(sys.stdin.readline().strip())
    for i in range(q):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print(lcs(x, y))



### FIXED CODE ###

def m():
 e=input
 a=''
 for _ in[0]*int(e()):
  X,z=e(),[]
  for y in e():
   s=i=0
   for k in z:
    t=X.find(y,s)+1
    if t<1:break
    if t<k:z[i]=t
    s=k;i+=1
   else:
    t=X.find(y,s)+1
    if t:z+=[t]
  a+=f'\n{len(z)}'
 print(a[1:])
if'__main__'==__name__:m()
### BUGGY CODE ###

N = int(input())
A = []
C = [0] * N
for i in range(N):
  s = str(input())
  if s in A:
    C[A.index(s)] += 1
  else:
    A.append(s)
  
m = max(C)
ans = [A[n] for n, v in enumerate(C) if v == m]
ans.sort()
for i in ans:
  print(i)

### FIXED CODE ###

N = int(input())
A = {}
for i in range(N):
  s = str(input())
  if s in A:
    A[s] += 1
  else:
    A[s] = 1

max_val = max(A.values())
keys = [key for key in A if A[key] == max_val]
keys.sort()
for s in keys:
  print(s)
### BUGGY CODE ###

import numpy as np
import math

n, d, a = map(int,input().split())
xh = np.zeros((n,2), dtype = int)
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]

num = 0
xh = xh[np.argsort(xh[:, 0])]

while xh.size > 0.5:
    nat = math.ceil((xh[0,1])/a)
    num += nat
    dam = nat*a
    for i in range(xh.shape[0]):
        if xh[i,0] <= xh[0,0]+2*d:
            xh[i,1] -= dam
        else:
            break
    xh = xh[~np.any(xh<0.5,axis=1)]

print(num)


### FIXED CODE ###

import math

n, d, a = map(int,input().split())
xh = [[0 for i in range(2)] for j in range(n)]
left = [i for i in range(n)]
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]

num = 0
xh.sort(key=lambda xh:xh[0])

for i in range(n):
    for j in range(left[i-1],i):
        if xh[j][0]+d >= xh[i][0]-d:
            left[i] = j
            break

dam = [0]*n

def dsum(k):
    if k == 0:
        return 0
    elif left[k] == 0:
        return dam[k-1]
    else:
        return dam[k-1]-dam[left[k]-1]

for i in range(n):
    res = xh[i][1]-dsum(i)
    nat = max([math.ceil(res/a),0])
    dam[i] = dam[i-1]+a*nat
    if res > 0:
        num += nat

print(num)
### BUGGY CODE ###

N, M = map(int,input().split())

banned_list = []
for i in range(M):
    banned_list.append(tuple(map(int,input().split())))
banned_list = sorted(banned_list,key=lambda x:x[1])
#status = [1 for _ in range(N-1)]
status = set()
counter = 0
for i in range(M):
    a = banned_list[i][0]
    b = banned_list[i][1]
    if len([one for one in status if (one >= a-1 and one < b-1)]) == 0:
        status  |= {b-2}
        counter += 1
print(counter)


### FIXED CODE ###

N, M = map(int,input().split())

banned_list = []
for i in range(M):
    banned_list.append(tuple(map(int,input().split())))
banned_list = sorted(banned_list,key=lambda x:x[1])
#status = [1 for _ in range(N-1)]
status = set()
counter = 0
for i in range(M):
    a = banned_list[i][0]
    b = banned_list[i][1]
    if len([one for one in status if (one >= a-1 and one < b-1)]) == 0:
        status  |= {b-2}
        counter += 1
print(counter)
### BUGGY CODE ###

n = int(input())
P = list(map(int, input().split()))
t = 0
for i in range(n):
  if min(P[:i+1]) >= P[i]:
    t += 1
print(t)

### FIXED CODE ###

n = int(input())
P = list(map(int, input().split()))
t = 1
m = P[0]
for i in range(1, n):
  if m > P[i]:
    m = P[i]
    t += 1
print(t)
### BUGGY CODE ###

import numpy as np
N,S=map(int,input().split())
As=list(map(int,input().split()))

MOD=998244353

#d = [[0]*3001 for _ in range(3001)]
d=np.zeros((3001,3001))
d[0][0]=1

for i in range(1,N+1):
    Ai=As[i-1]
    for j in range(S+1):
        d[i][j] += 2*d[i-1][j]
        if Ai <= j:
            d[i][j] += d[i-1][j-Ai]
        d[i][j] %= MOD
print(int(d[N][S]))


### FIXED CODE ###

import numpy as np
N,S=map(int,input().split())
As=list(map(int,input().split()))

MOD=998244353

#d = [[0]*3001 for _ in range(3001)]
d=np.zeros((3001,3001))
d[0,0]=1

for i in range(1,N+1):
    Ai=As[i-1]
    d[i] += 2*d[i-1]
    d[i,Ai:] += d[i-1][:-Ai]
    d[i] %= MOD
print(int(d[N][S]))
### BUGGY CODE ###

N,K=map(int,input().split())
c=0
if K%2==0:
    d=K//2
else:
    d=K

for i in range(d,N+1,d):
    for j in range(d,N+1,d):
        for k in range(d,N+1,d):
            if (i+j)%K==0 and (j+k)%K==0 and (k+i)%K==0:
                c+=1
print(c)

### FIXED CODE ###

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

if K%2==0:
    print((N//K)**3+((N//(K//2))-(N//K))**3)
else:
    print((N//K)**3)
### BUGGY CODE ###

import itertools

N = int(input())
a = [0]*N
b = [0]*N
for i in range(N):
    a[i], b[i] = [int(x) for x in input().split()]


p = list(itertools.permutations(zip(a, b)))

is_ok = False
for i in range(len(p)):
    w = 0
    for j in range(N):
        if w + p[i][j][0] <= p[i][j][1]:
            w += p[i][j][0]
            if j == N-1:
                is_ok = True
        else:
            break


print('Yes' if is_ok else 'No')


### FIXED CODE ###

N = int(input())
a = [0]*N
b = [0]*N
for i in range(N):
    a[i], b[i] = [int(x) for x in input().split()]

tasks = sorted(list(zip(a, b)), key=lambda x: x[1])

is_okay = True
sum = 0
for i in range(N):
    sum += tasks[i][0]

    if sum > tasks[i][1]:
        is_okay = False
        break

print('Yes' if is_okay else 'No')
### BUGGY CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint
from operator import itemgetter


def main():
    num = int(stdin.readline())

    L = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        L.append([(next(it), next(it)) for _ in xrange(next(it))])

    weight = [[maxint, i] for i in xrange(num)]
    weight[0][0] = 0
    V = set(xrange(1, num))
    W = weight[1:]
    index = 0

    while V:
        for v, cost in L[index]:
            if v not in V:
                continue
            weight[v][0] = min(weight[v][0], cost + weight[index][0])

        a = min(W, key=itemgetter(0))
        index = a[1]
        W.remove(a)
        V.remove(index)

    for d, i in weight:
        print(i, d)


main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxsize


def main():
    num = int(stdin.readline())

    edges = []
    for _ in range(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in range(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxsize] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxsize and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()
### BUGGY CODE ###

n=int(input())
import math
res=0
for a in range(1,n+1):
    for b in range(1, n + 1):
        for c in range(1, n + 1):
            li=[]
            for i in range(1,max(a,b,c)+1):
                if a%i==0 and b%i ==0 and c%i==0:
                    li+=[i]
            res+=max(li)
print(res)

### FIXED CODE ###

n=int(input())
import math
res=0
for a in range(1,n+1):
    for b in range(1, n + 1):
        gcd1 = math.gcd(a, b)
        for c in range(1, n + 1):
           gcd2=math.gcd(gcd1,c)
           res+=gcd2
print(res)
### BUGGY CODE ###

n = int(input())
l = [int(x) for x in input().split()]
def motomeru(i):
  m = l.count(i)
  return int(m*(m-1)/2)
def herasu(i):
  m = l.count(i)-1
  return int(m*(m-1)/2)
zenbu = 0
for i in range(n):
  zenbu = zenbu + motomeru(i+1)
for i in range(n):
  a = zenbu - motomeru(l[i]) + herasu(l[i])
  print(a)


### FIXED CODE ###

n = int(input())
l = [int(x) for x in input().split()]
k = [0]*n
for i in range(n):
  k[l[i] - 1] = k[l[i] - 1] + 1
def motomeru(i):
  return int((k[i-1])*(k[i-1]-1)/2)
def herasu(i):
  if k[i-1] == 0 or k[i-1] == 1:
    return 0
  else:
    return int((k[i-1]-1)*(k[i-1]-2)/2)
zenbu = 0
for i in range(n):
  zenbu = zenbu + motomeru(i+1)
for i in range(n):
  a = zenbu - motomeru(l[i]) + herasu(l[i])
  print(a)
### BUGGY CODE ###

import heapq

def main():
    n, m = map(int, input().split())
    dics = [{} for _ in range(n)]
    rmky = [set() for _ in range(n)]
    for _ in range(m):
        l, r, c = map(int, input().split())
        ky = (l-1, r-1)
        if ky in dics[l-1]:
            if c < dics[l-1][ky]:
                dics[l-1][ky] = c
        else:
            dics[l-1][ky] = c
        if r < n:
            rmky[r].add(ky)
    for i in range(1, n):
        dics[i].update(dics[i-1])
        for v in rmky[i]:
            dics[i].pop(v)
    dist = [float("inf")]*n
    dist[0] = 0
    hq = []
    heapq.heappush(hq, [0, 0])
    while len(hq) > 0:
        v, p = heapq.heappop(hq)
        if v > dist[p]:
            continue
        if p == n-1:
            break
        for l, r in dics[p].keys():
            for i in range(l, r+1):
                if i == p:
                    continue
                dics[i].pop((l, r))
                if dist[i] > v + dics[p][(l, r)]:
                    dist[i] = v + dics[p][(l, r)]
                    heapq.heappush(hq, [dist[i], i])
    if dist[n-1] == float("inf"):
        print(-1)
    else:
        print(dist[n-1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

import heapq

def main():
    n, m = map(int, input().split())
    dics = [{} for _ in range(n)]
    for _ in range(m):
        l, r, c = map(int, input().split())
        ky = r-1
        if ky in dics[l-1]:
            if c < dics[l-1][ky]:
                dics[l-1][ky] = c
        else:
            dics[l-1][ky] = c
    dist = [float("inf")]*n
    dist[0] = 0
    hq = []
    heapq.heappush(hq, [0, 0])
    idx = 0
    while len(hq) > 0:
        v, p = heapq.heappop(hq)
        if p < idx:
            continue
        if p == n-1:
            break
        for i in range(idx+1, p):
            if len(dics[i]) > 0:
                for ky in dics[i].keys():
                    if ky in dics[p]:
                        if dics[p][ky] > dics[i][ky]:
                            dics[p][ky] = dics[i][ky]
                    else:
                        if p < ky:
                            dics[p][ky] = dics[i][ky]
        idx = p
        for r in dics[p].keys():
            if dist[r] > v + dics[p][r]:
                dist[r] = v + dics[p][r]
                heapq.heappush(hq, [v + dics[p][r], r])
    if dist[n-1] == float("inf"):
        print(-1)
    else:
        print(dist[n-1])

if __name__ == "__main__":
    main()
### BUGGY CODE ###

# D - Partition
# Mの約数で、しかもN倍してもMを超えないもののうち、最大のものを探す

N, M = map(int, input().split())

x = 1

while x * N <= M:
    if M % x == 0:
        ans = x
    x += 1
    
print(ans)

### FIXED CODE ###

# D - Partition
# Mの約数で、しかもN倍してもMを超えないもののうち、最大のものを探す

N, M = map(int, input().split())

if N == 1:
    print(M)
    exit()

x = M//N

while 1:
    if M % x == 0:
        ans = x
        break
    x -= 1
    
print(ans)
### BUGGY CODE ###

n = int(input())
a = input().split(" ")
a = [int(i) for i in a]

#m = max(a)
r = -1

for i in range(len(a)):
  t = i + 1
  try:
    idx = a.index(t)
    a = a[(idx+1):]
    r = t
  except:
    break

if r < 0:
  print(r)
else:
  print(n - r)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
 
target = 1
ans = 0
 
for i in range(N):
    if a[i] == target:
        target += 1
    else:
        ans += 1
 
if ans == N:
    ans = -1
    
print(ans)
### BUGGY CODE ###

import numpy as np

num_of_numbers = int(input())
numbers = np.array(list(map(int, input().split())))
num_of_operation = int(input())
operations = []
for i in range(num_of_operation):
    B, C = map(int, input().split())
    numbers = np.where(numbers == B, C, numbers)
    print(sum(numbers))

### FIXED CODE ###

import collections

num_of_numbers = int(input())
numbers = list(map(int, input().split()))
num_of_operation = int(input())

# intで初期化するため0が返る
cnt = collections.defaultdict(int)
# numbersに含まれる各数字の出現回数を保持
for i in numbers:
    cnt[i] += 1

# 初期状態の和を算出
ans = sum(numbers)

for i in range(num_of_operation):
    B, C = map(int, input().split())

    # 置換対象の数字が存在する場合
    if B in cnt:
        tmpB = cnt[B]
        tmpC = cnt[C]
        ans = ans - (B * tmpB) + (C * tmpB)

        cnt[C] = tmpC + tmpB
        cnt.pop(B)

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

import sys
from fractions import gcd
input = sys.stdin.readline


def lcm(a, b):
    return a * b // gcd(a, b)


mod = 10**9+7
N = int(input())
A = list(map(int, input().split()))

ans = 0
prev = A[0]
for a in A:
    l = lcm(prev, a)
    factor = l // prev % mod
    ans = (ans * factor + l // a) % mod
    prev = l
print(ans)


### FIXED CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline


def mod_inverse(n, mod=10**9+7):
    return pow(n, mod-2, mod)

    
def lcm(a, b):
    return a * b // gcd(a, b)


mod = 10**9+7
N = int(input())
A = list(map(int, input().split()))

ans = 0
inv_sum = 0
l = A[0]
for a in A:
    l = lcm(l, a)
    inv_sum = (inv_sum + mod_inverse(a)) % mod
print(l * inv_sum % mod)
### BUGGY CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()
py = []
for _ in range(m):
    py.append(list(li()))

order = [[] for _ in range(n+1)]

for p,y in sorted(py, key=lambda x:x[1]):
    order[p].append(y)

cnt = [0]*(n+1)

for p,y in py:
    cnt[p] += 1
    ans = str(p).zfill(6) + str(order[p].index(y)+1).zfill(6)
    print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()
py = []
for _ in range(m):
    py.append(list(li()))

order = [{} for _ in range(n+1)]
cnt = [0]*(n+1)

for p,y in sorted(py, key=lambda x:x[1]):
    order[p].update({y: cnt[p]})
    cnt[p] += 1


for p,y in py:
    cnt[p] += 1
    ans = str(p).zfill(6) + str(order[p][y]+1).zfill(6)
    print(ans)
### BUGGY CODE ###

n = int(input())
k = str(input())
R = [i for i in range(0, n) if k[i] == 'R']
G = [i for i in range(0, n) if k[i] == 'G']
B = [i for i in range(0, n) if k[i] == 'B']

ans = 0
for rx in R:
	for gx in G:
		for bx in B:
			a = [rx, gx, bx]
			a.sort()
			ans += (1 if a[1] - a[0] != a[2] - a[1] else 0)
print(ans)

### FIXED CODE ###

n = int(input())
k = str(input())

k += '.'*n

R = [0] * (n*3)
G = [0] * (n*3)
B = [0] * (n*3)

dic = { 'R' : 0, 'G' : 0, 'B' : 0 };
for i in range(n-1, -1, -1):
    dic[k[i]] += 1
    R[i] = dic['R']
    G[i] = dic['G']
    B[i] = dic['B']

ans = 0
for i in range(n):
    for j in range(i+1, n):
        if k[i] != k[j]:
            charset = ['R', 'G', 'B'];
            charset.remove(k[i]);
            charset.remove(k[j]);
            ##
            if charset[0] == 'R':
                ans += R[j + 1]
                ans -= (1 if k[j + (j - i)] == 'R' else 0)
            if charset[0] == 'G':
                ans += G[j + 1]
                ans -= (1 if k[j + (j - i)] == 'G' else 0)
            if charset[0] == 'B':
                ans += B[j + 1]
                ans -= (1 if k[j + (j - i)] == 'B' else 0)

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

import math
L,A,B,M = map(int, input().split())

d = 0
for i in reversed(range(L)):
  if (d == 0):
    keta = 0
  else:
    keta = int(math.log10(d))+1
  d = (d + 10**keta * (A + B*i))

print(d % M)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
import numpy as np
input = sys.stdin.readline

L,A,B,M = map(int, input().split())

C = []
for i in range(19):
  C.append(min(max(0,(10**i - A - 1) //B + 1), L))

def R_mul(A, B, M):
  return np.mod((np.dot(A,B)), M)

def R_pow(R, n, M):
  if n == 1:
    return R
  
  R2 = R_mul(R, R, M)
  R2 = R_pow(R2, n//2, M)
  
  if n % 2 == 0:
    return R2
  else:
    return R_mul(R2, R, M)

                 
ans = 0
R = np.ones((3,3))
s = np.array([0, A%M, 1])

for d in range(1,19):
  r = C[d] - C[d-1]
  if (0 == r):
    continue
  R0 = np.array([[pow(10,d,M),1,0],[0,1,(B%M)],[0,0,1]])
  R = R_pow(R0, r, M)
  s = R_mul(R, s, M)
  #print(d, R, s)
  if (C[d] > L):
    break

print(s[0])
### BUGGY CODE ###

import sys
N = int(input())
c = input()
ans = 0
exchange = 0
for i in range(N):
    if c[i] == "W":
        exchange = i
        break
else:
    print(0)
    sys.exit()

for i in range(N):
    # print(i+1,"回目")
    # print("exchange=",exchange)
    # print("c=",c)
    if N-i > exchange:
        if c[-(i+1)] =="R":
            # c = list(c)
            # c[exchange] = "R"
            # c[-(i+1)] = "W"
            # c = "".join(c)
            c = c[:exchange]+"R"+c[exchange+1:]
            # print("newc=",c)
            c = c[:-(i+1)]+"W"+c[N-i:]
            # print("newc=",c)
            ans += 1
            for k in range(exchange+1,N):
                if c[k] == "W":
                    exchange = k
                    break
            else:
                break
    else:
        break
print(ans)

### FIXED CODE ###

import sys
N = int(input())
c = input()
ans = 0
exchange = 0
for i in range(N):
    if c[i] == "W":
        exchange = i
        break
else:
    print(0)
    sys.exit()

for i in range(N):
    if N-i > exchange:
        if c[-(i+1)] =="R":
            # c = list(c)
            # c[exchange] = "R"
            # c[-(i+1)] = "W"
            # c = "".join(c)
            # c = c[:exchange]+"R"+c[exchange+1:]
            # print("newc=",c)
            # c = c[:-(i+1)]+"W"+c[N-i:]
            # print("newc=",c)
            ans += 1
            for k in range(exchange+1,N-(i+1)):
                if c[k] == "W":
                    exchange = k
                    break
            else:
                break
    else:
        break
print(ans)
### BUGGY CODE ###

def factors(n):
    sieve = [1]*(n+10)
    ret = []
    m = 1
    while m*7-1 <= n:
        for p in [m*7-1,m*7+1]:
            if sieve[p] == 0: continue
            if n%p == 0:
                ret.append(p)
            for pp in range(2*p,n+1,p):
                sieve[pp] = 0
        m += 1
    return(ret)

while True:
    N = int(input())
    if N == 1: break
    ans = ' '.join(list(map(str,factors(N))))
    print('{0}: {1}'.format(N,ans))

### FIXED CODE ###

MAXN = 300010
sieve = [1]* MAXN
primes = []
for n in range(7,MAXN,7):
    for m in [n-1,n+1]:
        if sieve[m] == 0: continue
        primes.append(m)
        for l in range(2*m,MAXN,m):
            sieve[l] = 0

def solve(n):
    ret = []
    for p in primes:
        if p > n: break
        if n%p == 0:
            ret.append(p)
    return ret

while True:
    N = int(input())
    if N == 1: break
    ans = ' '.join(list(map(str,solve(N))))
    print('{0}: {1}'.format(N,ans))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
while all(A % 2 == 0 for A in a):
    A = [i / 2 for i in a]
    ans += 1
print(ans)


### FIXED CODE ###

import numpy as np
n = int(input())
a = list(map(int, input().split()))
cnt = 0
while True:
    for i in range(n):
        if a[i] % 2 == 1:
            print(cnt)
            quit()
        a[i] /= 2
    cnt += 1
print(cnt)
### BUGGY CODE ###

import math
k = int(input())
ans = 0
x = 10**9 + 7
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += math.gcd(math.gcd(a, b), c)
            ans = ans % x
print(ans)


### FIXED CODE ###

from math import gcd
k = int(input())
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        d = gcd(a, b)
        for c in range(1, k+1):
            ans += gcd(d, c)
print(ans)