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

s = str(input())
now = [0] * 2019
mod = 2019
ans,cnt = 0,1
lis = [int(s[-(1+i)]) for i in range(len(s))]
for num in lis:
    now[0] += 1
    num *= cnt
    num %= mod
    next = [0] * mod
    for i in range(2019-num):
        next[num+i] += now[i]
    for i in range(num):
        next[i] += now[2019-num+i]
    ans += next[0]
    cnt *= 10
    cnt %= mod
    now = next
print(ans)

### FIXED CODE ###

s = str(input())
now = [0] * 2019
mod = 2019
ans,cnt = 0,1
lis = [int(s[-(1+i)]) for i in range(len(s))]
for num in lis:
    now[0] += 1
    num *= cnt
    num %= mod
    next = [0] * mod
    for i in range(2019-num):
        next[num+i] += now[i]
    for i in range(num):
        next[i] += now[2019-num+i]
    ans += next[0]
    cnt *= 10
    cnt %= mod
    now = next
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
s = s.replace('R', '0')
s = s.replace('G', '1')
s = s.replace('B', '2')

s0 = [0] * (n + 5)
s1 = [0] * (n + 5)
s2 = [0] * (n + 5)

for i in range(n):
    s0[i + 1] = s0[i] + (s[i] == '0')
    s1[i + 1] = s1[i] + (s[i] == '1')
    s2[i + 1] = s2[i] + (s[i] == '2')

#print(s0)
#print(s1)
#print(s2)

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        if s[i] == s[j]: continue
        h = 99 - (ord(s[i]) + ord(s[j]))
        if h == 0:
            ans += s0[n] - s0[j]
            if 2 * j - i < n and s[2 * j - i] == '0': ans -= 1
        if h == 1:
            ans += s1[n] - s1[j]
            if 2 * j - i < n and s[2 * j - i] == '1': ans -= 1
        if h == 2:
            ans += s2[n] - s2[j]
            if 2 * j - i < n and s[2 * j - i] == '2': ans -= 1
        #print(i, j, h, ans)
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
s = s.replace('R', '0')
s = s.replace('G', '1')
s = s.replace('B', '2')

s0 = [0] * (n + 5)
s1 = [0] * (n + 5)
s2 = [0] * (n + 5)

for i in range(n):
    s0[i + 1] = s0[i] + (s[i] == '0')
    s1[i + 1] = s1[i] + (s[i] == '1')
    s2[i + 1] = s2[i] + (s[i] == '2')

#print(s0)
#print(s1)
#print(s2)

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        if s[i] == s[j]: continue
        h = 99 - (ord(s[i]) + ord(s[j]))
        if h == 0:
            ans += s0[n] - s0[j]
            if 2 * j - i < n and s[2 * j - i] == '0': ans -= 1
        if h == 1:
            ans += s1[n] - s1[j]
            if 2 * j - i < n and s[2 * j - i] == '1': ans -= 1
        if h == 2:
            ans += s2[n] - s2[j]
            if 2 * j - i < n and s[2 * j - i] == '2': ans -= 1
        #print(i, j, h, ans)
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
Query = [list(map(str, input().split())) for i in range(Q)]

reverse = 0

for i in range(Q):
  if len(Query[i]) == 1:
    reverse += 1
  else:
    if Query[i][1] == '1':
      if reverse % 2 == 0:
        S = Query[i][2] + S
      else:
        S = S + Query[i][2]
    else:
      if reverse % 2 == 0:
        S = S + Query[i][2]
      else:
        S = Query[i][2] + S
        
ans = ''
if reverse % 2 == 0:
  ans = S
else:
  ans = S[::-1]
  
print(ans)

### FIXED CODE ###

S = input()
Q = int(input())
Query = [list(map(str, input().split())) for i in range(Q)]

reverse = 0
b = []
a = []

for i in range(Q):
  if len(Query[i]) == 1:
    reverse += 1
  else:
    if Query[i][1] == '1':
      if reverse % 2 == 0:
        b.append(Query[i][2])
      else:
        a.append(Query[i][2])
    else:
      if reverse % 2 == 0:
        a.append(Query[i][2])
      else:
        b.append(Query[i][2])
        
ans = ''
s = (''.join(b))[::-1] + S + ''.join(a)
if reverse % 2 == 0:
  ans = s
else:
  ans = s[::-1]
  
print(ans)
### BUGGY CODE ###

import sys,math

N,A,B=map(int,input().split())
H = [0] * N
H = [int(input()) for i in range(N)]
 
maxH = max(H)
L=-1
R=math.ceil(maxH / B)

while R-L>1:
    MID=(L+R)//2
    SUM=0
    for i in range(N):
        SUM+=max(0,math.ceil(max(H[i]-B*MID,0)/(A-B)))

    if SUM>MID:
        L=MID
    else:
        R=MID

print(R)


### FIXED CODE ###

import math

N,A,B=map(int,input().split())
H = [0] * N
H = [int(input()) for i in range(N)]

maxH = max(H)
L=-1
R=math.ceil(maxH / B)

def binary_search(D,U):
    MID=(D+U)//2
    if(MID==D):
        print(U)
    else:
        if sum(math.ceil(max(h-B*MID,0)/(A-B))for h in H)<=MID:
            binary_search(D,MID)
        else:
            binary_search(MID,U)


binary_search(L,R)
### BUGGY CODE ###

d={i:0 for i in range(13)}
d[0]=1
s=input()
for k,t in enumerate(s[::-1]):
    if t=='?':
        d2={i:0 for i in range(13)}
        for i in range(10):
            u=(i*10**k)%13
            for i in range(13):
                d2[(i+u)%13]+=d[i]
    else:
        u=(int(t)*10**k)%13
        d2={i:0 for i in range(13)}
        for i in range(13):
            d2[(i+u)%13]+=d[i]
    for i in range(13):
        d[i]=d2[i]%(10**9+7)
print(d[5])

### FIXED CODE ###

d=[0]*13
d[0]=1
s=input()
for k,t in enumerate(s[::-1]):
    if t=='?':
        d2=[0]*13
        for i in range(10):
            u=i*pow(10,k,13)
            for i in range(13):
                d2[(i+u)%13]+=d[i]
    else:
        u=int(t)*pow(10,k,13)
        d2=[0]*13
        for i in range(13):
            d2[(i+u)%13]+=d[i]
    for i in range(13):
        d[i]=d2[i]%(10**9+7)
print(d[5])
### BUGGY CODE ###

def prime_factor(n):
    factors = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0:
            factors.append(i)
            n = n//i
    if n!=1:
        factors.append(n)
    return factors

N = int(input())
li = prime_factor(N)
a = len(li)
ans = 10**9
for i in range(2**a):
    tmp1 = tmp2 = 1
    for j in range(a):
        if ((i>>j) & 1):
            tmp1 *= li[j]
        else:
            tmp2 *= li[j]
    tmp3 = max(len(str(tmp1)),len(str(tmp2)))
    if ans>tmp3:
        ans = tmp3
print(ans)

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    #divisors.sort()
    return divisors

N = int(input())
list =  make_divisors(N)
ans = 10**9
if len(list)%2==1:
    list.append(list[-1])
for i in range(0,len(list),2):
    tmp1 = len(str(list[i]))
    tmp2 = len(str(list[i+1]))
    ans = min(ans,max(tmp1,tmp2))
print(ans)
### BUGGY CODE ###

row = int(input())
item_list = [input() for i in range(row)]
result_list = []
for j in item_list:
  exist_in_item_list = False
  for k in result_list:
    if j == k:
      exist_in_item_list = True
      break
  if not exist_in_item_list:
    result_list.append(j)

print(len(result_list))


### FIXED CODE ###

row = int(input())
item_list = [input() for i in range(row)]
print(len(set(item_list)))
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
array = []
for i in range(Q):
    m,n = [int(x) for x in input().split()]

    for j in range(len(A)):
        if m == A[j]:
            A[j] = n
    print(sum(A))

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
array = []
replace = [0]*(10**5+1)
for i in A:
    replace[i] += 1
sum_s = sum(A)
for i in range(Q):
    m,n = [int(x) for x in input().split()]
    replace[n] += replace[m]

    diff = n*replace[m] - replace[m]*m
    sum_s += diff
    replace[m] = 0
    print(sum_s)
### BUGGY CODE ###

def gcd(a,b):
	i = a
	j = b
	while i!=j:
		if i > j:
			i = i-j
		else :
			j = j - i
	return i

k = int(input())

ret = 0
for i in range(1,k+1):
	for j in range(1,k+1):
		for l in range(1,k+1):
			g = gcd(i,gcd(j,l))
			#print("i:",i," j:",j," l:",l," gcd:", g)
			ret += g
print(ret)

### FIXED CODE ###

def gcd(a,b):
	i = a
	j = b
	while i!=j:
		if i > j:
			i = i-j
		else :
			j = j - i
	return i

k = int(input())

ret = 0
for i in range(1,k+1):
	for j in range(i,k+1):
		for l in range(j,k+1):
			g = gcd(i,gcd(j,l))
			if (i == j) and (j == l):
				m = 1
			elif (i == j) or (j == l) or (l == i):
				m = 3
			else :
				m = 6
			#print("i:",i," j:",j," l:",l," gcd:", g," m:",m)
			ret += g*m
print(ret)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# ABC155_C
N = int(input())
S = [str(input()) for _ in range(N)]

SS = list(set(S))
M = len(SS)

lst = [0]*M
for i in range(M):
    lst[i] = S.count(SS[i])

ans = []
for j in range(M):
    if lst[j] == max(lst):
        ans.append(SS[j])

ans = sorted(list(set(ans)))
for a in ans:
    print(a)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# ABC155_C
import collections

N = int(input())
s = [str(input()) for _ in range(N)]

S = collections.Counter(s)
M = S.most_common()[0][1]
S = sorted(S.most_common())

for i in range(len(S)):
    if S[i][1] == M:
        print(S[i][0])
### BUGGY CODE ###

from collections import deque
N=int(input())
A=deque(list(map(int,input().split())))
D={}
ans=""
M=0
for i in range(N):
    a=A.pop()
    if N//(N-i)==1:
        D[N-i]=a
        if a==1:
            M+=1
            ans=ans+str(N-i)+" "
    else:
        p=N//(N-i)
        memo=0
        for j in range(1,p):
            memo+=D[(N-i)*(j+1)]
        if memo%2==a:
            D[N-i]=0
        else:
            D[N-i]=1
            M+=1
            ans=ans+str(N-i)+" "
ans=ans[:-1]
print(M)
print(ans)

### FIXED CODE ###

from collections import deque
N=int(input())
A=deque(list(map(int,input().split())))
D={}
ans=[]
M=0
for i in range(N):
    a=A.pop()
    if N//(N-i)==1:
        D[N-i]=a
        if a==1:
            M+=1
            ans.append(str(N-i))
    else:
        p=N//(N-i)
        memo=0
        for j in range(1,p):
            memo+=D[(N-i)*(j+1)]
        if memo%2==a:
            D[N-i]=0
        else:
            D[N-i]=1
            M+=1
            ans.append(str(N-i))
print(M)
print(" ".join(ans))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

n, a, b, k = map(int, input().split())

nmemo = [0 for i in range(n+1)]
def permutation(n):
    if nmemo[n] != 0:
        return nmemo[n]
    if n == 0:
        return 1
    nmemo[n] = n * permutation(n-1)
    return nmemo[n]


memo = []
ans = 0

for i in range(n + 1):
    knum = k - b * i
    if k < 0:
        break
    if knum % a == 0 and knum//a <= n:
        memo.append([knum // a, i])

for i in memo:
    nmin = min(i[0], i[1])
    jmin = 0
    if i[0] + i[1] > n:
        jmin = i[0] + i[1] - n
    for j in range(jmin, nmin+1):
        if (i[0] + i[1] - j) <= n:
            ans += permutation(n) // (permutation(i[0] - j) * permutation(i[1] - j)
                                      * permutation(j) * (permutation(n - (i[0] - j + i[1]))))

if k == 0:
    print(1)
else:
    print(ans % 998244353)

### FIXED CODE ###

n, a, b, k = map(int, input().split())

mod = 998244353

# combination---
# nとmodは適宜変える

fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n+5):
    fac.append(fac[i-1] * i % mod)
    inv.append(mod - inv[mod%i] * (mod//i) % mod)
    finv.append(finv[i-1] * inv[i] % mod)

def nck(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 0
for ca in range(n+1):
    cb = (k - a * ca) // b
    if (k - a * ca) % b != 0:
        continue
    ans += nck(n, ca) * nck(n, cb)
    ans %= mod

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

from collections import Counter

n = int(input())
s = [x for x in [Counter(list(input())) for _ in range(n)]]


alphabet = set('abcdefghijklmnopqrstuvwxyz')
s_list = [int(''.join([str(s_i[a]) for a in alphabet])) for s_i in s]

count = 0
i = 0

for x in s_list:
  i += 1
  temp = s_list[i:]
  hoge = s[i:]
  for y in temp:
    if y == x:
      count += 1
print(count)

### FIXED CODE ###

def sort_str(s):
  temp = sorted(list(s))
  return ''.join(list(temp))

n = int(input())
s = [input() for _ in range(n)]

s_dict = {}
count = 0

for s_i in s:
  k = sort_str(s_i)
  if k in s_dict:
    count += s_dict[k]
    s_dict[k] += 1
  else:
    s_dict[k] = 1
    
print(count)
### BUGGY CODE ###

N = int(input())
print(sum(range(N)))

### FIXED CODE ###

N = int(input())
print((N * (N - 1)) // 2)
### BUGGY CODE ###

N = int(input())
array = list(map(int, input().split()))
sameNum = [0]*(N)

for i in range(N):
    sameNum[array[i]-1] += 1

for k in range(1, N+1):
    answer = 0
    sameNumT = sameNum[:]
    sameNumT[array[k-1]-1] -= 1
    for l in range(N):
        answer += sameNumT[l]*(sameNumT[l]-1)//2
    print(answer)

### FIXED CODE ###

N = int(input())
array = list(map(int, input().split()))
sameNum = [0]*(N)
sum = 0
# kを削除していないlistでの組み合わせを調べる
for i in range(N):
    sameNum[array[i]-1] += 1
for i in range(N):
    sum += sameNum[i]*(sameNum[i]-1)//2

for k in range(1, N+1):
    sumT = sum
    print(sumT - sameNum[array[k-1]-1] + 1)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
v=sum(a)
for i in range(n-1):
    if k<a[i]+a[i+1]:
        while k<a[i]+a[i+1]:
            a[i+1]=a[i+1]-1
print(v-sum(a))

### FIXED CODE ###

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

from heapq import *
from collections import defaultdict
from copy import deepcopy
from math import log
from itertools import accumulate
from collections import deque

n,m,s,t=map(int,input().split())
s-=1
t-=1
INF=10**19
Gyen=[[]for i in range(n)]
Gsnu=[[]for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  Gyen[u].append([v,a])
  Gyen[v].append([u,a])
  Gsnu[u].append([v,b])
  Gsnu[v].append([u,b])

def dijkstra(G,s):
  que=[]
  d=[INF]*n
  d[s]=0
  heappush(que,[0,s])
  while(que):
    p=heappop(que)
    v=p[1]
    if d[v]<p[0]:
      continue
    for i in range(len(G[v])):
      e=G[v][i]
      if d[e[0]]>d[v]+e[1]:
        d[e[0]]=d[v]+e[1]
        heappush(que,[d[e[0]],e[0]])
  return d

yen=dijkstra(Gyen,s)
snu=dijkstra(Gsnu,t)
l=[INF]
for i in range(n-1,-1,-1) :
  l.append(min(l[-1],yen[i]+snu[i]))
for i in l[n:0:-1]:
  print(10**15-i)


### FIXED CODE ###

from heapq import *

n,m,s,t=map(int,input().split())
s-=1
t-=1
INF=10**19
Gyen=[[]for i in range(n)]
Gsnu=[[]for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  Gyen[u].append([v,a])
  Gyen[v].append([u,a])
  Gsnu[u].append([v,b])
  Gsnu[v].append([u,b])

def dijkstra(G,s):
  que=[]
  d=[INF]*n
  d[s]=0
  visited={s}
  heappush(que,[0,s])
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,[d[node],node])
  return d

yen=dijkstra(Gyen,s)
snu=dijkstra(Gsnu,t)
ans=10**15
ans_list=[]
for i in reversed(range(n)):
  ans=min(ans,yen[i]+snu[i])
  ans_list.append(10**15-ans)
print(*ans_list[::-1], sep='\n')
### BUGGY CODE ###

n = int(input())
s = input()

digit_numbers = [v for v in range(len(s))]
num_set = set()

import itertools
for p in itertools.permutations(digit_numbers, 3):
    p = sorted(list(p))
    num = s[p[0]] + s[p[1]] + s[p[2]]
    num_set.add(num)
print(len(num_set))

### FIXED CODE ###

n = int(input())
s = input()

counter = 0
for i in range(10):
    str_i = str(i)
    i_dig = s.find(str_i)
    if i_dig == -1:
        continue

    for j in range(10):
        str_j = str(j)
        j_dig = s.find(str_j, i_dig+1)
        if j_dig == -1:
            continue
        
        for k in range(10):
            str_k = str(k)
            k_dig = s.find(str_k, j_dig+1)
            if k_dig != -1:
                counter += 1

print(counter)
### BUGGY CODE ###

from collections import Counter

n = int(input())
sss = [input() for _ in range(n)]
d = {s[1:]: 0 for s in sss}
flags = [1 << (i * 18) for i in range(26)]

for s in sss:
    cnt = Counter(s)
    flag = 0
    for c in cnt:
        flag |= flags[ord(c) - 97]
    if '' in d:
        d[''] += flag
    for i in range(len(s) - 1, 0, -1):
        c = s[i]
        cnt[c] -= 1
        if cnt[c] == 0:
            flag ^= flags[ord(c) - 97]
        if s[i:] in d:
            d[s[i:]] += flag

ans = 0
mask = (1 << 18) - 1
for s in sss:
    cnt = (d[s[1:]] >> ((ord(s[0]) - 97) * 18)) & mask
    ans += cnt - 1

print(ans)


### FIXED CODE ###

from collections import Counter

n = int(input())
sss = [input() for _ in range(n)]
d = {s[1:]: 0 for s in sss}
flags = [1 << (i * 18) for i in range(26)]

trie_chr = [-1]
trie_children = [{}]
trie_counter = [0]
trie_fin = [0]
s_fin_node = []
l = 1

for s in sss:
    node = 0
    trie_counter[node] += 1
    for i in range(len(s) - 1, 0, -1):
        c = ord(s[i]) - 97
        if c in trie_children[node]:
            node = trie_children[node][c]
            trie_counter[node] += 1
        else:
            trie_chr.append(c)
            trie_children.append({})
            trie_fin.append(0)
            trie_children[node][c] = l
            trie_counter.append(1)
            node = l
            l += 1
    trie_fin[node] += 1
    s_fin_node.append(node)

trie_flags = [0] * l

for s in sss:
    cnt = Counter(s)
    flag = 0
    for c in cnt:
        flag |= flags[ord(c) - 97]
    node = 0
    if len(s) > 1 and trie_fin[node] > 0:
        trie_flags[node] += flag

    for i in range(len(s) - 1, 1, -1):
        c = s[i]
        k = ord(c) - 97
        cnt[c] -= 1
        if cnt[c] == 0:
            flag ^= flags[k]

        node = trie_children[node][k]
        # print(s, i, node, trie_counter[node])
        if trie_counter[node] == 1:
            break
        if trie_fin[node] > 0:
            trie_flags[node] += flag
            # print('add', s, i)

# print([chr(c) if c >= 0 else -1 for c in trie_chr])
# print(trie_counter)
# print(trie_fin)
# print(trie_flags)
# print(s_fin_node)

ans = 0
mask = (1 << 18) - 1
for i, s in enumerate(sss):
    cnt = (trie_flags[s_fin_node[i]] >> ((ord(s[0]) - 97) * 18)) & mask
    ans += cnt

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

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

#dp[i]:i番目に到達するまでにはらうコストの最小値
INF = float('inf')
dp = [INF for i in range(N)]
dp[0] = 0

for i in range(0,N):
    for k in range(1, K+1):
        if i+k > N-1:
            break
        dp[i+k] = min(dp[i+k], dp[i]+abs(h[i+k]-h[i]))


print(dp[N-1])

### FIXED CODE ###

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

#dp[i]:i番目に到達するまでにはらうコストの最小値
INF = float('inf')
dp = [INF for i in range(N)]
dp[0] = 0

for i in range(0,N):
    for k in range(1, K+1):
        if i+k > N-1:
            break
        dp[i+k] = min(dp[i+k], dp[i]+abs(h[i+k]-h[i]))


print(dp[N-1])
### BUGGY CODE ###

k=0
s=0
combi = 0

def nyu():
    num1,num2 = input().split()
    k = int(num1)
    s = int(num2)
    return k,s

def calc(l_k,l_s):
    l_combi = 0
    for x in range(l_k):
        if check1(s,l_s) == True:
            break
        for y in range(l_k):
            if check2(x,y,l_s) == True :
               break
            for z in range(l_k):
                if check3(x,y,z,l_s) == True :
                    break
    #            print("x=",x,"y=",y,"z=",z)
                sum = x+y+z
                if l_s == sum:
                    l_combi +=1
                    
    return l_combi

def check1(x,s):
    if x<s:
        return True
    return False

def check2(x,y,s):
    sum = x+y
    if s<sum:
        return True
    return False

def check3(x,y,z,s):
    sum = x+y+z
    if s<sum:
        return True
    return False    


k,s=nyu()
print(calc(k+1,s))









### FIXED CODE ###

k=0
s=0
combi = 0

def nyu():
    num1,num2 = input().split()
    k = int(num1)
    s = int(num2)
    return k,s

def calc(l_k,l_s):
    l_combi = 0
    for x in range(l_k):
#        check_tmp =0
#        check_tmp =check1(x,l_s,l_k)
#        if check_tmp == 1:
#            break
#        elif check_tmp  == 2:
#            continue
        for y in range(l_k):
#            check_tmp =check2(x,y,l_s,l_k)
#            if check_tmp == 1:
#                break
#            elif check_tmp  == 2:
#                continue2
#            sum = x+y+l_k 
            sum = l_s- x-y 
            if 0<=sum and sum <= k:
#                print("x=",x,"y="   ,y) 
                l_combi +=1
    return l_combi

def check1(x,s,k):
    if s<x:
        return 1
    if x+(k-1)*2 < s:
        return 2
    return 0

def check2(x,y,s,k):
    sum = x+y
    if s<sum:
        return 1
    if x+y+k-1 < s:
       return 2
    return 0

def check3(x,y,z,s):
    sum = x+y+z
    if s<sum:
        return 1
    return 0    

def check_ini(k,s):
    if k*3 < s:
        return True
    return False


k,s=nyu()
if check_ini == True:
    print("0")
else :
    print(calc(k+1,s))
### BUGGY CODE ###

S = input()
mod = 10**9+7
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1

for i, s in enumerate(S[::-1], start=1):
    m = pow(10, i-1, 13)
    if s=="?":
        for j in range(10):
            for k in range(13):
                dp[i][(j*m+k)%13] += dp[i-1][k]
    else:
        j = int(s)
        for k in range(13):
            dp[i][(j*m+k)%13] += dp[i-1][k]
    
    for j in range(13):
        dp[i][j] %= mod

print(dp[-1][5])

### FIXED CODE ###

S = input()
mod = 10**9+7
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1

for i, s in enumerate(S[::-1], start=1):
    m = pow(10, i-1, 13)
    if s=="?":
        for j in range(10):
            for k in range(13):
                dp[i][(j*m+k)%13] += dp[i-1][k]
    else:
        j = int(s)
        for k in range(13):
            dp[i][(j*m+k)%13] += dp[i-1][k]
    
    for j in range(13):
        dp[i][j] %= mod

print(dp[-1][5])
### BUGGY CODE ###

import math
inf=float('inf')
N = int(input())
x = list(map(int, input().split()))
y = []

for i in range(N):
    y.append(x[i])
    y.reverse()


for i in range(len(y)):
    print(y[i],end=' ')

quit()

### FIXED CODE ###

import math
inf=float('inf')
N = int(input())
x = list(map(int, input().split()))
y = [0]*(N)
j=0
for i in range(0,N,1):
    
    if i%2==0:
        y[j]=x[N-1-i]
  
    if i%2==1:
        y[N-1-j]=x[N-1-i]
        j+=1
    
    


for i in range(len(y)):
    print(y[i],end=' ')
 
quit()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
x=1
flag=0
for i in range(len(a)):
    x*=a[i]
    if x>10**18:
        flag=1
if 0 in a:
    flag=2
if flag==0:
    print(x)
elif flag==1:
    print(-1)
else:
    print(0)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
x=1
flag=0
for i in range(len(a)):
    x*=a[i]
    if x>10**18:
        flag=1
        break
if 0 in a:
    flag=2
if flag==0:
    print(x)
elif flag==1:
    print(-1)
else:
    print(0)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
count = 1
broke = 0
suceed = False
while True:
    if count in a:
        suceed = True
        broke += a.index(count)
        a = a[a.index(count) + 1:]
        count += 1
    else:
        broke += len(a)
        break
if suceed:
    print(broke)
else:
    print(-1)


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
count = 1
broke = 0

if 1 not in a:
    print(-1)
    exit()

for x in range(N):
    if a[x] == count:
        count += 1

print(N - count + 1)
### BUGGY CODE ###

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

### FIXED CODE ###

N, A, B = map(int, input().split())
ab = A + B
cnt = N // ab
remain = N - (cnt * ab)
blue = 0
if remain > A:
    blue = A
else:
    blue = remain
ans = A * cnt + blue
print(ans)