Harryxun/stf_run huggingface dataset:
input(); a = sorted(map(int, input().split()), reverse=True)
print(sum(a[0::2])-sum(a[1::2]))

### FIXED CODE ###

n = int(input())
L0, L1 = 2, 1
while True:
    if n == 1:
        print(L1)
        exit()
    L0 += L1
    n -= 1
    if n == 1:
        print(L0)
        exit()
    L1 += L0
    n -= 1
from collections import Counter
s = input().rstrip()
cnt = Counter(s)
a = list(cnt.values())
a.sort()
if (a[2] - a[0]) > 1:
    print("NO")
else:
    print("YES")

### FIXED CODE ###

from collections import Counter
s = input().rstrip()
n = len(s)
cnt = Counter(s)
a = list(cnt.values())
while len(a) < 3:
    a.append(0)
a.sort()
if a[2] - a[0] < 2:
    print("YES")
else:
    print("NO")
s = input()
K = int(input())

ans = []
for i in range(K):
  for j in range(len(s)-i):
    c = s[j:j+i+1]
    if (i != 0 and c.count(c[0]) == len(c)):
      c = "".join(set(c))
    ans.append(c)
  
set_ans = sorted(set(ans))
print(set_ans[K-1])


### FIXED CODE ###

s = input()
K = int(input())
S = set()
ans = []
for i in range(K):
  for j in range(len(s)-i):
    c = s[j:j+i+1]
    S.add(c)
  
set_ans = sorted(list(S))
print(set_ans[K-1])
a, b, c, d, e, f = map(int, input().split())

w = 0
s = 0
ratio = 0

for i in range(31):
    for j in range(31):
        water = a*i + b*j
        for k in range(1501):
            l = 0
            hoge = 1024
            while hoge:
                nl = l+hoge
                sugar = k*c+nl*d
                if 0 < water and water*100 + sugar <= f and sugar <= water*e:
                    l = nl
                hoge >>= 1
            sugar = k*c+l*d
            if ratio <= sugar / (water*100+sugar):
                w = water*100
                s = sugar
                ratio = sugar / (water*100+sugar)

print("%d %d"%(w+s,s))


### FIXED CODE ###

a,b,c,d,e,f = map(int, input().split(' '))

w = 0
s = 0
ratio = 0

for i in range((f // (b*100))+1):
    for j in range(((f-(i*b*100))//(a*100))+1):
        if i == 0 and j == 0:
            continue
        smax = min(f-(j*a+i*b)*100,(j*a+i*b)*e)
        sm = 0
        for k in range((smax//d)+1):
            sm = max(sm, k*d+c*((smax-(k*d))//c))
        if ratio <= sm/((j*a+i*b)*100+sm):
            ratio = sm/((j*a+i*b)*100+sm)
            w = (j*a+i*b)*100
            s = sm


print("%i %i" %(w+s,s))
a,b = map(int, input().split())

if a >= 13:
  print(b)
elif 6 <= a && a <= 12:
  print(b/12)
else:
  print(0)

### FIXED CODE ###

a,b = map(int, input().split())
 
if a >= 13:
  print(b)
elif 6 <= a and a <= 12:
  print(int(b/2))
else:
  print(0)
# -*- coding: utf-8 -*-

a=input()

s=48-a

print(s)


### FIXED CODE ###

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

a=int(input())

s=48-a

print(s)
s = input()
if s[5::6] <= 04 and s[8::9] <= 30:
  print("Heisei")
else:
  print("TBD")

### FIXED CODE ###

s = input()
if s <= "2019/04/30":
  print("Heisei")
else:
  print("TBD")
N,X = map(int,input().split())

def f(a,b) :
    if a < b :
        return 2*a + f(a,b-a)
    elif b == 0 :
        return 0
    else :
        return ((a//b)*2-1)*b

ans = N + f(X,N-X)

print(ans)


### FIXED CODE ###

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

def f(a,b) :
    if a > b :
        a,b = b,a
    if b % a == 0 :
        return 2*(b//a-1)*a + a
    else :
        return 2*(b//a)*a + f(a,b%a)
        
ans = N + f(X,N-X)

print(ans)
import math

def nCr(n,r):
    f = math.factorial
    return int(f(n) / f(r) / f(n-r))

def nHk(n, k):
    f = math.factorial
    return int(f(n + k - 1) // f(k) // f(n - 1))

N, K = map(int, input().split())
MOD = 10 ** 9 + 7

for i in range(1, K + 1):
#    print('i: ' + str(i))
    # 青玉をi個のグループに並べる並べ方
    blue = 1
#    if i == 1:
#        blue = 1
#    else:
#        blue = nCr(K - 1, i - 1)
#    print('blue: ' + str(blue))
    # 青い玉に合わせた赤い玉の並べ方
    if (N - K) <= (i - 1):
        red = 0
#        print('red0: ' + str(red))
    elif i == 1:
        red = (N - K) + 1
#        print('red1: ' + str(red))
    else:
        red = nCr(K - 1, i - 1) * nHk(i + 1, N - K - (i - 1))
#        print('nCr: ' + str(nCr(K - 1, i - 1)))
#        print('nHk: ' + str(nHk(i + 1, N - K - (i - 1))))
#        print('red2: ' + str(red))

    # 解は青の並べ方と赤の並べ方の組み合わせ
    ans = blue * red % MOD
    print(ans)
#    print('ans: ' + str(ans))


### FIXED CODE ###

from operator import mul
from functools import reduce

def nCr(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N, K = map(int, input().split())
MOD = 10 ** 9 + 7

for i in range(1, K + 1):
    if i > N - K + 1:
        ans = 0
    else:
        ans = nCr(K - 1, i - 1) * nCr(N - K + 1, i) % MOD
    print(ans)
import bisect
INF = 10 ** 9 + 7
N, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
aset = set(a)
bset = set(b)
ablst = [0] * ((N * M) + 1)
a.sort(), b.sort()

if len(aset) != len(a) or len(bset) != len(b):
    print(0)
    exit()

for i in range(N):
    ablst[a[i]] += 1

for j in range(M):
    ablst[b[j]] += 1

ans = 1
for i in range(N * M, 0, -1):
    ac = bisect.bisect_left(a, i)
    bc = bisect.bisect_left(b, i)
    if ablst[i] == 2:
        ans *= 1
    elif ablst[i] == 1 and a[ac] == i:
        ans *= (M - bc)
    elif ablst[i] == 1 and b[bc] == i:
        ans *= (N - ac)
    else:
        acnt = bisect.bisect_left(a, i)
        bcnt = bisect.bisect_left(b, i)
        ans *= (N - ac) * (M - bc) - (N * M - i)
    ans %= INF
print(ans % INF)

### FIXED CODE ###

import bisect
INF = 10 ** 9 + 7
N, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
aset = set(a)
bset = set(b)
ablst = [0] * ((N * M) + 1)
a.sort(), b.sort()

if len(aset) != len(a) or len(bset) != len(b):
    print(0)
    exit()

for i in range(N):
    ablst[a[i]] += 1

for j in range(M):
    ablst[b[j]] += 1

ans = 1
for i in range(N * M, 0, -1):
    ac = bisect.bisect_left(a, i)
    bc = bisect.bisect_left(b, i)
    if ablst[i] == 2:
        ans *= 1
    elif ablst[i] == 1 and ac < N and a[ac] == i:
        ans *= (M - bc)
    elif ablst[i] == 1 and bc < M and b[bc] == i:
        ans *= (N - ac)
    else:
        acnt = bisect.bisect_left(a, i)
        bcnt = bisect.bisect_left(b, i)
        ans *= (N - ac) * (M - bc) - (N * M - i)
    ans %= INF
print(ans % INF)
A, B = map(int, input().split())

ans = 0
taps = 1

while True:
	if taps >= B:
		print(ans)
		break
	taps += (A - 1)
	ans += 1
A, B = map(int, input().split())

ans = 0
taps = 1

while True:
	if taps >= B:
		print(ans)
		break
	taps += (A - 1)
	ans += 1


### FIXED CODE ###

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

ans = 0
taps = 1

while True:
	if taps >= B:
		print(ans)
		break
	taps += (A - 1)
	ans += 1
N, K = map(int, input().split())
S = list(input().split())
S[K-1] = S[K-1].lower()
print("".join(S))

### FIXED CODE ###

N, K = map(int, input().split())
S = list(input())
S[K-1] = S[K-1].lower()
print("".join(S))
N = int(input())
a = list(map(int, input().split()))
b = []
for i in range(N):
    b.append([a[i], i+1])
b.sort(reverse = True)
ans = [0]*(N+1)
mini = N+1

for i in range(N-1):
    mini = min(mini, b[i][1])
    if b[i+1][0] - b[i][0] < 0:
        ans[mini] += (b[i][0] - b[i+1][0])*(i+1)

ans[1] += N*min(b)
for i in range(N):
    print(ans[i+1])


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
b = []
for i in range(N):
    b.append([a[i], i+1])
b.sort(reverse = True)
ans = [0]*(N+1)
mini = N+1

for i in range(N-1):
    mini = min(mini, b[i][1])
    if b[i+1][0] - b[i][0] < 0:
        ans[mini] += (b[i][0] - b[i+1][0])*(i+1)

ans[1] += N*b[-1][0]
for i in range(N):
    print(ans[i+1])
S =input()
if int(S[:4])<2018:
  print("Heisei")
elif int(S[:4])>2019:
  print("TBD")
else:
  if int(S[6:8])>4:
    print("TBD")
  else:
    print("Heisei")

### FIXED CODE ###

import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    S = input()
    if int(S[:4]) < 2018:
        print("Heisei")
    elif int(S[:4]) > 2019:
        print("TBD")
    else:
        if int(S[5:7]) > 4:
            print("TBD")
        else:
            print("Heisei")

if __name__ == "__main__":
    main()
N, M = (int(x) for x in input().split())
import collections
Parent = [i for i in range(N)]
def fp(i):
    global Parent
    if Parent[i] == i:
        return i
    else:
        Parent[i] == fp(Parent[i])
        return Parent[i]

for _ in range(M):
    a, b = (int(x) for x in input().split())
    Parent[max(a,b)-1] = fp(min(a,b)-1)

Groupsize = collections.defaultdict(lambda:0)
for i in range(N):
    i = fp(i)
    Groupsize[i] +=1
ans = max(gs for gs in Groupsize.values())
print(ans)

### FIXED CODE ###

N, M = (int(x) for x in input().split())
import collections
Parent = [i for i in range(N)]
def fp(i):
    global Parent
    if Parent[i] == i:
        return i
    else:
        Parent[i] = fp(Parent[i])
        return Parent[i]

for _ in range(M):
    a, b = (int(x) for x in input().split())
    par_a, par_b = fp(a-1), fp(b-1)
    if par_a < par_b:
        Parent[par_b] = par_a
    else:
        Parent[par_a] = par_b

Groupsize = collections.defaultdict(lambda:0)
for i in range(N):
    i = fp(i)
    Groupsize[i] +=1
ans = max(gs for gs in Groupsize.values())
print(ans)
d, n = map(i, input().split())
 
if d==0:
  print(n)
if d==1:
  print(n*100)
if d==2:
  print(n*10000)
  

### FIXED CODE ###

d, n = map(int, input().split())
 
if d==0:
	if n<100:
		print(n)
	else:
		print(101)    
elif d==1:
	if n<100:
		print(n*100)
	else:
		print(10100)
elif d==2:
	if n<100:
		print(n*10000)
	else:
		print(n*10000+10000)
s=input()
if s="AAA","AAB","ABA","ABB","BBA","BAB","BBA":
    print("Yes")
else:
    print("No")

### FIXED CODE ###

S=set(input())

if len(S)==1:
    print("No")
else:
    print("Yes")
N = int(input())
S = input()
#dp[i][j] S[i-x:i+1]==S[j-x:j+1]となる最大のx
dp = [[0] * (N + 1) for _ in range(N + 1)]
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            dp[i][j] = min(dp[i - 1][j - 1] + 1, j - i)
    ans = max(ans, dp[i])
print(ans)


### FIXED CODE ###

import itertools
N = int(input())
S = input()
dp = [[0] * N for _ in range(N)]
ans = 0
for i, j in itertools.combinations(range(N), 2):
    if S[i] == S[j]:
        dp[i][j] = dp[i - 1][j - 1] + 1
    else:
        dp[i][j] = 0
    ans = max(ans, min(j - i, dp[i][j]))
print(ans)
import math

x = input().split(" ")
a = int(x[0])
b = int(x[1])
c = int(x[2])
d = int(x[3])

c_count = (b//c)-((a-1)//c)
d_count = (b//d)-((a-1)//d)

cd = c*d // math.gcd(c,d)
cd_count = (b//cd) - ((a-1)//cd)
ans = (b+1-a)-c_count-d_count+cd_count

print(ans)


### FIXED CODE ###

import fractions

x = input().split(" ")
a = int(x[0])
b = int(x[1])
c = int(x[2])
d = int(x[3])

c_count = (b//c)-((a-1)//c)
d_count = (b//d)-((a-1)//d)

cd = c*d // fractions.gcd(c,d)
cd_count = (b//cd) - ((a-1)//cd)
ans = (b+1-a)-c_count-d_count+cd_count

print(ans)
N = int(input())
A = list(map(int, input().split()))
A = sorted(A,reverse=True)
ans = 1
if 0 in A:
    print(0)
    quit()
else:
    for i in A:
        ans *=A[i]
        if ans>= 10**18:  
            print(-1)
            quit()
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A = sorted(A,reverse=True)
B = 1
if 0 in A:
    print(0)
    quit()
else:
    for i in A:
        B *= i
        if B> 10**18:  
            print(-1)
            quit()
print(B)
n,m,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]

def make_sumlist(book_list):
    sumnum=0
    container=[0]
    for i in book_list:
        container.append(sumnum+i)
        sumnum+=i
    return container

total_a=make_sumlist(a)
total_b=make_sumlist(b)

# print(n,m,k)
# print(total_a)
# print(total_b)


#r個読めるか
def readable(r):
    #全部読んでも無理
    if r>n+m:
        return False
    
    max_book=100000000000
    for a_n in range(max(0,r-m),min(n,r)+1):
        b_n=r-a_n
        # print(a_n,b_n)
        book_sum=total_a[a_n]+total_b[b_n]
        # print(book_sum)
        max_book=min(max_book,book_sum)
    if max_book<=k:
        return True
    return False

readable(4)


def nibuntansaku(start,end):
    if start==end:
        return start
    middle=(start+end)//2
    if readable(middle):
        start=middle
    else:
        end=middle-1
    return nibuntansaku(start,end)

print(nibuntansaku(1,k))


### FIXED CODE ###

n,m,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]

def make_sumlist(book_list):
    sumnum=0
    container=[0]
    for i in book_list:
        container.append(sumnum+i)
        sumnum+=i
    return container

total_a=make_sumlist(a)
total_b=make_sumlist(b)

# print(n,m,k)
# print(total_a)
# print(total_b)


#r個読めるか
def readable(r):
    #全部読んでも無理
    if r>n+m:
        return False
    if r==0:
        return True
    max_book=100000000000
    for a_n in range(max(0,r-m),min(n,r)+1):
        b_n=r-a_n
        # print(a_n,b_n)
        book_sum=total_a[a_n]+total_b[b_n]
        # print(book_sum)
        max_book=min(max_book,book_sum)
    if max_book<=k:
        return True
    return False

def nibuntansaku(start,end):
    if start==end:
        return start
    middle=(start+end)//2+1
    if readable(middle):
        start=middle
    else:
        end=middle-1
    return nibuntansaku(start,end)

print(nibuntansaku(0,k))
N, M = map(int, input().split())
G = [[] for _ in range(N)]
in_G = [0] * N

for i in range(M):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    in_G[y-1] += 1

dist = [0] * N
q = [x for x in range(N) if in_G[x] == 0]

while q:
    v = q.pop

    for g in G[v]:
        dist[g] = max(dist[g], dist[v] + 1)
        in_G[g] -= 1
        if in_G[g] == 0:
            q.append(g)

print(max(dist))

### FIXED CODE ###

N, M = map(int, input().split())
G = [[] for _ in range(N)]
in_G = [0] * N

for i in range(M):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    in_G[y-1] += 1

dist = [0] * N
q = [x for x in range(N) if in_G[x] == 0]

while q:
    v = q.pop()

    for g in G[v]:
        dist[g] = max(dist[g], dist[v] + 1)
        in_G[g] -= 1
        if in_G[g] == 0:
            q.append(g)

print(max(dist))
def flog(l) :
    if len(l) <= 1 :
        res = 0
    elif len(l) == 2 :
        res = abs(l[1]-l[0])
    else :
        a = abs(l[2]-l[0])
        b = abs(l[1]-l[0])
        if a <= b :
            res = a + flog(l[2:])
        else :
            res = b + flog(l[1:])
    return res

N = int(input())
H = list(map(int,input().split()))
H = list(reversed(H))

print(flog(H))


### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
dp = [0 for i in range(N)]
if N >= 3 :
    
    for i in range(1,3) :
        dp[i] = abs(L[i]-L[0])
    for i in range(3,len(dp)) :
        a = dp[i-1] + abs(L[i]-L[i-1])
        b = dp[i-2] + abs(L[i]-L[i-2])
        dp[i] = min(a,b)
    print(dp[N-1])
    #print(dp)

else :
    print(abs(L[-1]-L[0]))
N = int(input())
H = list(map(int, input().split()))

ans = "Yes"

for i in range(N-2):
    if H[i] - 1 > H[i+1] or H[i] - 1 > H[i+2]:
        ans = "No"
        break
if H[-2] - 1 > H[-1] and ans == "Yes":
    ans = "No"


print(ans)

### FIXED CODE ###

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

flag = True

for i in range(N-1, 0, -1):
    if H[i-1] - 1 == H[i]:
        H[i-1] -= 1
    elif H[i-1] - 1 > H[i]:
        flag = False
        break

if flag:
    print("Yes")
else:
    print("No")
n,k=map(int,input().split())
ls=list(map(int,input().split()))
ps=[]
length=0
goto=1
for _ in range(100):
    idx=goto-1
    goto=ls[idx]
    if goto==-1:
        break
    ps.append(goto)
    ls[idx]=-1
    length+=1

amari=(k-1)%3
print(ps[amari])

### FIXED CODE ###

n,k=map(int,input().split())
ls=list(map(int,input().split()))
check_ls=[0 for i in range(n)]
ps=[1]
nxt=1
while True:
    idx=nxt-1
    if check_ls[idx]==-1:
        break
    ps.append(ls[idx])
    nxt=ls[idx]
    check_ls[idx]=-1

loop_start_idx = ps.index(ps[-1])
loop_length=len(ps)-loop_start_idx-1
loop_ls=ps[loop_start_idx:-1]
if k<len(ps):
    print(ps[k])
else:
    idx=(k-loop_start_idx)%loop_length
    print(loop_ls[idx])
def gcd(a,b):
        while b!=0:
                a,b=b,a%b
        return a

A, B, C, D = map(int, input().split(" "))
ans = 0
Bc = B // C
Bd = B // D
ck = 0

asb = C*D//ck
Bs = B//asb

newb = B - Bc - Bd + Bs

Ac = (A-1) // C
Ad = (A-1) // D
As = (A-1)//asb

newa = (A-1)-Ac-Ad+As

print(int(newb-newa))

### FIXED CODE ###

def gcd(a,b):
        while b!=0:
                a,b=b,a%b
        return a

A, B, C, D = map(int, input().split(" "))
ans = 0
Bc = B // C
Bd = B // D
ck = gcd(C,D)
asb = C*D//ck
Bs = B//asb

newb = B - Bc - Bd + Bs

Ac = (A-1) // C
Ad = (A-1) // D
As = (A-1)//asb

newa = (A-1)-Ac-Ad+As

print(int(newb-newa))
x,a,b=map(int,input().split())
    if abs(x-a)<abs(b-x):
        print('A')
    else:
        print('B')


### FIXED CODE ###

x,a,b=map(int,input().split())
y=abs(x-a)
z=abs(b-x)
if y<z:
    print('A')
else:
    print('B')
h,a = map(int,input().split())
print(h//a+not not h%a)

### FIXED CODE ###

h,a = map(int,input().split())
print(h//a+(not not h%a))
a,b,c=map(int,input().split())
if a=b=c:
  print(1)
elif a=b!=c:
  print(3)
else:
  print(6)

### FIXED CODE ###

n=int(input())
print(n*n*n)
S = str(input())
if(S=="Sunny"):
    print("Cloudy")
else if(S=="Cloudy"):
    print("Rainy")
else if(S=="Rainy"):
    print("Sunny")
else:
    exit()

### FIXED CODE ###

S = str(input())
if(S=="Sunny"):
    print("Cloudy")
elif(S=="Cloudy"):
    print("Rainy")
elif(S=="Rainy"):
    print("Sunny")
else:
    exit()
#ABC145D
def main():
    import sys, math
    X, Y = map(int, sys.stdin.readline().split())
    '''
    i +2*j ==X
    2*i +j ==Y
    '''
    if (2*Y-X)%3==0:
        i = (2*Y-X)//3
        j = Y-2*i
    else:
        ans =0
    #print(i, j)
    mod = 10**9+7
    def calc(n):
        ans = 1
        for i in range(n, 1, -1):
            ans *= i
            ans %= mod
        return ans
    
    ans = calc(i+j)
    #print(calc(-1))
    #print(ans)
    
    #calc2(calc(i), mod-2)
    gg1 = pow(calc(i), mod-2, mod)
    gg2 = pow(calc(j), mod-2, mod)
    
    if i<0 or j<0:
        print(0)
    elif i==0 and j==0:
        print(0)
    else:
        print(ans*gg1*gg2%mod)

if __name__=='__main__':
    main()

### FIXED CODE ###

#ABC145D
def main():
    import sys, math
    X, Y = map(int, sys.stdin.readline().split())
    '''
    i +2*j ==X
    2*i +j ==Y
    '''
    if (2*Y-X)%3==0:
        i = (2*Y-X)//3
        j = Y-2*i
    else:
        i,j=0,0
    #print(i, j)
    mod = 10**9+7
    def calc(n):
        ans = 1
        for i in range(n, 1, -1):
            ans *= i
            ans %= mod
        return ans
    
    ans = calc(i+j)
    #print(calc(-1))
    #print(ans)
    
    #calc2(calc(i), mod-2)
    gg1 = pow(calc(i), mod-2, mod)
    gg2 = pow(calc(j), mod-2, mod)
    
    if i<0 or j<0:
        print(0)
    elif i==0 and j==0:
        print(0)
    else:
        print(ans*gg1*gg2%mod)

if __name__=='__main__':
    main()
a,b=input().split()
h=int(a)
w=int(b)
if h ==0 and w==0:
   break
for i in range(h):
   print("#"*w)


   

### FIXED CODE ###

while True:
    a,b=map(int,input().split())
    if a==0 and b==0:
        break
    for i in range(a):
        print("#"*b)
    print("")
X = int(input())
n = 0
money = 100
while(money<X){
  money = money+money//100
  n = n+1
}
print(n)


### FIXED CODE ###

X = int(input())
n = 0
money = 100
while(money<X):
  money = money+money//100
  n = n+1
print(n)
from functools import lru_cache

MOD = 10 ** 9 + 7

@lru_cache(maxsize=None)
def r(k, smaller):
    global s

    if k == len(s):
        return 1

    if smaller:
        if s[k] == "1":
            return (2 * r(k + 1, True) + r(k + 1, False)) % MOD
        else:
            return r(k + 1, True) % MOD
    else:
        return (3 * r(k + 1, False)) % MOD


s = input()
print(r(0, True))


### FIXED CODE ###

import sys
from functools import lru_cache

sys.setrecursionlimit(1000000000)

MOD = 10 ** 9 + 7

@lru_cache(maxsize=None)
def r(k, smaller):
    global s

    if k == len(s):
        return 1

    if smaller:
        if s[k] == "1":
            return (2 * r(k + 1, True) + r(k + 1, False)) % MOD
        else:
            return r(k + 1, True) % MOD
    else:
        return (3 * r(k + 1, False)) % MOD


s = input()
print(r(0, True))
from string import ascii_lowercase
N = int(input())
     
k = [0, 26]
for i in range(1, 13):
  k.append(26 * (k[i] + 1))
     
  for i in range(13):
    if k[i] + 1 <= N <= k[i+1]:
      n = N - (k[i] + 1)
     
      for j in range(i, -1, -1):
        print(ascii_lowercase[(n//26**j) % 26], end="")


### FIXED CODE ###

N = int(input())
L = list("abcdefghijklmnopqrstuvwxyz")
a = 1
while N > 26**a:
    N = N - 26**a
    a += 1
 
pre = []
for i in reversed(range(1,a)):
    r = (N-1) // 26**i
    pre.append(r)
    N = int(N%(26**i))
 
ans = ''
for i in pre:
    ans += L[i]
print(ans+L[N-1])
a,b,c = [int(i) for i in input().split()]
i=0
for i in range(a,b+1,1):
    if c % i == 0:
        i = i+1
    else:
        
print(i)


### FIXED CODE ###

a,b,c = [int(i) for i in input().split()]
i=0
for num in range(a,b+1,1):
    if c % num == 0:
        i = i+1
    else:
        pass
print(i)
n,a,b = map(int,input().split())
cnt = 0
ball = ''
while cnt<n:
    ball += 'b'*a
    ball += 'r'*b
    cnt += a+b
print(ball.count('b',0,n))

### FIXED CODE ###

n,a,b = map(int,input().split())
print((n//(a+b))*a+min(n%(a+b),a))
#coding:utf-8
import bisect,math
import multiprocessing
A,B,Q=map(int,raw_input().split())
s=[0]*A
t=[0]*B
for i in range(A):
    s[i]=input()
for a in range(B):
    t[i]=input()
buf=[]
def f(x):
    sl=bisect.bisect_left(s,x)-1
    sr=bisect.bisect_left(s,x)
    tl=bisect.bisect_left(t,x)-1
    tr=bisect.bisect_left(t,x)
    ans=float("inf")
    if sl!=-1 and tl!=-1:
        A=max(s[sl],t[tl])
        B=min(s[sl],t[tl])
        L=abs(x-A)+abs(A-B)
        ans=min(ans,L)
    if sl!=-1 and tr!=len(t):
        L=abs(x-s[sl])*2 + abs(t[tr]-x)        
        ans=min(ans,L)
        ans=min(ans,abs(x-s[sl])+abs(t[tr]-x)*2)
    if tl!=-1 and sr!=len(s):
        ans=min(ans,abs(x-t[tl])*2+abs(s[sr]-x))
        ans=min(ans,abs(x-t[tl])+abs(s[sr]-x)*2)
    if tr!=len(t) and sr!=len(s):
        A=min(s[sr],t[tr])
        B=max(s[sr],t[tr])
        L=abs(A-x)+abs(B-A)
        ans=min(ans,L)
    return str(ans)

I=[0]*Q
for i in xrange(Q):
    I[i]=input()
r=map(f,I)
print("\n".join(r))
    
    




### FIXED CODE ###

#coding:utf-8
import bisect,sys
A,B,Q=map(int,raw_input().split())
s=[0]*A
t=[0]*B
for i in range(A):    
    s[i]=int(sys.stdin.readline())
for i in range(B):
    t[i]=int(sys.stdin.readline())
buf=[]
def f(x):
    sl=bisect.bisect_left(s,x)-1
    sr=sl+1
    tl=bisect.bisect_left(t,x)-1
    tr=tl+1
    ans=float("inf")
    if sl!=-1 and tl!=-1:
        A=max(s[sl],t[tl])
        B=min(s[sl],t[tl])
        L=abs(x-A)+abs(A-B)
        ans=min(ans,L)
    if sl!=-1 and tr!=len(t):
        L=abs(x-s[sl])*2 + abs(t[tr]-x)        
        ans=min(ans,L)
        ans=min(ans,abs(x-s[sl])+abs(t[tr]-x)*2)
    if tl!=-1 and sr!=len(s):
        ans=min(ans,abs(x-t[tl])*2+abs(s[sr]-x))
        ans=min(ans,abs(x-t[tl])+abs(s[sr]-x)*2)
    if tr!=len(t) and sr!=len(s):
        A=min(s[sr],t[tr])
        B=max(s[sr],t[tr])
        L=abs(A-x)+abs(B-A)
        ans=min(ans,L)
    return str(ans)

I=[0]*Q
for i in xrange(Q):
    I[i]=int(sys.stdin.readline())
r=map(f,I)
print("\n".join(r))