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

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
done = [[10**4 + 1]*(W) for _ in range(H)]

min_count = 10 ** 4 + 1

def dfs(h, w, before_black, count):
    if maze[h][w] == "#":
        is_black = True
        if not before_black:
            count += 1
    else:
        is_black = False
    if done[h][w] < count:
        return
    done[h][w] = count
    if h == H-1 and w == W-1:
        global min_count
        if count < min_count:
            min_count = count
    elif h == H-1:
        dfs(h, w+1, is_black, count)
    elif w == W-1:
        dfs(h+1, w, is_black, count)
    else:
        dfs(h+1, w, is_black, count)
        dfs(h, w+1, is_black, count)

dfs(0,0,False,0)

print(min_count)


### FIXED CODE ###

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
done = [[10**4 + 1]*(W) for _ in range(H)]

min_count = 10 ** 4 + 1

def dfs(h, w, before_black, count):
    if maze[h][w] == "#":
        is_black = True
        if not before_black:
            count += 1
    else:
        is_black = False
    if done[h][w] <= count:
        return
    done[h][w] = count
    if h == H-1 and w == W-1:
        global min_count
        if count < min_count:
            min_count = count
    elif h == H-1:
        dfs(h, w+1, is_black, count)
    elif w == W-1:
        dfs(h+1, w, is_black, count)
    else:
        dfs(h+1, w, is_black, count)
        dfs(h, w+1, is_black, count)

dfs(0,0,False,0)
print(min_count)
### BUGGY CODE ###

#D
n = int(input())
l = [0] *( n + 1)
for i in range(1, n + 1):
    for j in range(i, n + 1, i):
        l[j] += 1
ans = 0
for i in range(n + 1):
    ans += l[i] * i
print(ans)

### FIXED CODE ###

#D
n = int(input())
#約数の数を求める＞＞倍数であり、n以下であるものの総和を求める

ans = 0
for i in range(1, n + 1):
    #iの倍数の数を求める
    m = n // i
    #初項i:公差i:m項までの等比数列の和
    ans += m * (2 * i + i * (m - 1)) *0.5
print(int(ans))
### BUGGY CODE ###

n,k=map(int,input().split())
heights=[int(i) for i in input().split()]

dp=[0]*n
dp[1]=abs(heights[1]-heights[0])

for i in range(2,n):
  step=[]
  for j in range(1,min(k+1,i+1)):
      step.append(dp[i-j]+abs(heights[i]-heights[i-j]))
    
  dp[i]=min(step)
print(dp[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
heights=[int(i) for i in input().split()]

dp=[0]*n
dp[1]=abs(heights[1]-heights[0])

for i in range(2,n):
  step=[]
  for j in range(1,min(k+1,i+1)):
      step.append(dp[i-j]+abs(heights[i]-heights[i-j]))
    
  dp[i]=min(step)
print(dp[n-1])
### BUGGY CODE ###

n = int(input())

num_list = [i+1 for i in range(n)]

best_ans = 0

for i in range(n - 1):
  best_ans += num_list[i] % num_list[i + 1]

print(best_ans)

### FIXED CODE ###

n = int(input())

print(n*(n-1) // 2)
### BUGGY CODE ###

N, Q = input().strip().split()
N = int(N)
Q = int(Q)
S = input()

for q_i in range(Q):
  l, r = input().strip().split()
  l = int(l)-1
  r = int(r)  
  subs = S[l:r]
  answer = 0
  for j, c in enumerate(subs):
    if j==0:
      pass
    else:
      if subs[j] == 'C' and subs[j-1] == 'A':
        answer += 1
  print(answer)

### FIXED CODE ###

N, Q = input().strip().split()
N = int(N)
Q = int(Q)
S = input()

counts = [0 for _ in range(len(S))]
for i in range(1, len(S)):
  if S[i] == 'C' and S[i-1] == 'A':
    counts[i] = counts[i-1] + 1
  else:
    counts[i] = counts[i-1]
    
for q_i in range(Q):
  l, r = input().strip().split()
  l = int(l)-1
  r = int(r)-1  
  print(counts[r] - counts[l])
### BUGGY CODE ###

N = int(input())
x = [None]*N
y = [None]*N
h = [None]*N

for i in range(N):
    x[i],y[i],h[i] = map(int, input().split())

def height(X,Y,xn,yn,hn):
    return hn+abs(X-xn)+abs(Y-yn)

def check(x,y,h,X,Y,H):
    for n in range(N):
        if h[n]>0:
            if height(X,Y,x[n],y[n],h[n])!=H:
                return False
        else:
            if H-abs(X-x[n])-abs(Y-y[n])>0:
                return False
    return True

for X in range(101):
    for Y in range(101):
        for n in range(N):
            H = height(X,Y,x[n],y[n],h[n])
            if check(x,y,h,X,Y,H) is True:
                print(X,Y,H)
                exit()


### FIXED CODE ###

N = int(input())
x = [None]*N
y = [None]*N
h = [None]*N

for i in range(N):
    x[i],y[i],h[i] = map(int, input().split())

def height(X,Y,xn,yn,hn):
    return hn+abs(X-xn)+abs(Y-yn)

def check(x,y,h,X,Y,H):
    for n in range(N):
        if h[n]>0:
            if height(X,Y,x[n],y[n],h[n])!=H:
                return False
        elif H-abs(X-x[n])-abs(Y-y[n])>0:
            return False
    return True

for X in range(101):
    for Y in range(101):
        for n in range(N):
            if h[n]>0:
                H = height(X,Y,x[n],y[n],h[n])
                if check(x,y,h,X,Y,H) is True:
                    print(X,Y,H)
                    exit()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    s = []
    for i in range(N):
        tmp = inputInt()
        s.append(tmp)
        
    ans = 0
    indexx = 2**len(s)
    for i in range(indexx):
        ten = 0
        for j in range(100):
            tmp = i >> j
            if 1 == tmp & 1:
                ten += s[j]
        
        if ten % 10 == 0:
            ten = 0
        
        if ans < ten:
            ans = ten
            
    print(ans)
        
        
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    s = []
    flg = False
    onry = False
    tmp_max = 0
    tmp_arr = []
    for i in range(N):
        tmp = inputInt()
        s.append(tmp)
        if tmp % 10 != 0:
            tmp_max += tmp
            tmp_arr.append(tmp)
            flg = True
            if onry == False:
                onry = True
            else:
                onry = None
            
    if flg == False:
        print(0)
        sys.exit()
        
    if onry == True or tmp_max % 10 != 0:
        print(sum(s))
        sys.exit()
        
    print(sum(s)-min(tmp_arr))
        
        
if __name__ == "__main__":
	main()
### BUGGY CODE ###

import numpy as np

def is_prime(a):
  if a == 1:
    return False
  
  for i in range(2, 1+int(a**0.5)):
    if a % i == 0:
      return False
  return True

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input())

ans = 0
z = 2

while True:
  if z > n:
    break
  if is_prime(n):
    ans += 1
    break
    
  if n % z != 0:
    z += 1
    continue
  
  tmp_divisors = make_divisors(z)
  for p in tmp_divisors[1:]:
    if not is_prime(p):
      continue
    tmp = np.log(z)/np.log(p)
    if tmp > 0 and tmp == int(tmp):
      n = n/z
      ans += 1
      z += 1
      break
  else:
    z += 1

print(ans)

### FIXED CODE ###

import numpy as np

def is_prime(a):
  if a == 1:
    return False
  
  for i in range(2, 1+int(a**0.5)):
    if a % i == 0:
      return False
  return True

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input())

ans = 0
divisors = make_divisors(n)
for d in divisors[1:]:
  if d > n:
    break
  if is_prime(n):
    ans += 1
    break
    
  tmp_divisors = make_divisors(d)
  for p in tmp_divisors[1:]:
    if not is_prime(p):
      continue
    tmp = np.log(d)/np.log(p)
    if tmp > 0 and tmp == int(tmp) and n % d == 0:
      n = n/d
      ans += 1
      break

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

L = int(input())

import random

vol_max = 0

for i in range(100000000):
    a = random.uniform(0, L)
    b = random.uniform(0, L-a)
    c= L-a-b
    vol = a*b*c
    if vol_max < vol: vol_max = vol
    else: continue
        
print(vol_max)

### FIXED CODE ###

L = int(input())

import random

print(L**3/27)
### BUGGY CODE ###

n, m = map(int, input().split())
abc = [list(map(int, input().split())) for x in range(m)]
nodes = [[] for x in range(n + 1)]

for a, b, c in abc:
    nodes[a].append([a, b, -c])

costs = [None for x in range(n + 1)]
costs[1] = 0
flg = True
for i in range(n - 1):
    for a, b, c in abc:
        if costs[a] == None:
            continue
        if costs[b] == None or costs[b] < costs[a] + c:
            flg = False
            costs[b] = costs[a] + c
    # for node in nodes[1:]:
    #     for a, b, c in node:
    #         if costs[a] == None:
    #             continue
    #         if costs[b] == None or costs[b] > costs[a] + c:
    #             flg = False
    #             costs[b] = costs[a] + c

ans = costs[n]
negative = [False for x in range(n + 1)]
for i in range(n - 1):
    for a, b, c in abc:
        if costs[a] == None:
            continue
        if costs[b] == None or costs[b] < costs[a] + c:
            costs[b] = costs[a] + c
            negative[b] = True

        if negative[a] == True:
            negative[b] = True

print(negative[n] and "inf" or ans)
#     if flg:
#         print(costs[n])
#         break
#     flg = True
# else:
#     print("inf")
#


### FIXED CODE ###

n, m = map(int, input().split())
abc = [list(map(int, input().split())) for x in range(m)]
nodes = [[] for x in range(n + 1)]

for a, b, c in abc:
    nodes[a].append([a, b, -c])

costs = [None for x in range(n + 1)]
costs[1] = 0
flg = True
for i in range(n):
    for a, b, c in abc:
        if costs[a] == None:
            continue
        if costs[b] == None or costs[b] < costs[a] + c:
            flg = False
            costs[b] = costs[a] + c
    # for node in nodes[1:]:
    #     for a, b, c in node:
    #         if costs[a] == None:
    #             continue
    #         if costs[b] == None or costs[b] > costs[a] + c:
    #             flg = False
    #             costs[b] = costs[a] + c
#     if flg:
#         print(costs[n])
#         break
#     flg = True
# else:
#     print("inf")

ans = costs[n]
negative = [False for x in range(n + 1)]
for i in range(n - 1):
    for a, b, c in abc:
        if costs[a] == None:
            continue
        if costs[b] == None or costs[b] < costs[a] + c:
            costs[b] = costs[a] + c
            negative[b] = True

        if negative[a] == True:
            negative[b] = True

print(negative[n] and "inf" or ans)
### BUGGY CODE ###

import bisect
N = int(input())
A = [int(input()) for i in range(N)]
B = [A[0]]
tmp = [0]*N
ans = 1
for i in range(1, N):
    id = bisect.bisect_left(B, A[i])
    if id == 0:
        bisect.insort_left(B, A[i])
    else:
        B[id-1] = A[i]
print(len(B))


### FIXED CODE ###

import bisect
import sys
import collections
input = sys.stdin.readline
N = int(input())
A = [int(input()) for i in range(N)]
B = [A[0]]
B = collections.deque(B)
tmp = [0]*N
ans = 1
for i in range(1, N):
    id = bisect.bisect_left(B, A[i])
    if id == 0:
        B.appendleft(A[i])
    else:
        B[id-1] = A[i]
print(len(B))
### BUGGY CODE ###

N, M = [int(i) for i in input().strip().split()]
A = [int(i) for i in input().strip().split()]
B = [0] * M
C = [0] * M
for i in range(M):
    B[i], C[i] = [int(i) for i in input().strip().split()]

A.sort()
for i in range(M):
    is_changed = False
    for j in range(0, B[i]):
        if A[j] < C[i]:
            A[j] = C[i]
            is_changed = True
        else:
            break
    if is_changed:
        A.sort()
print(sum(A))


### FIXED CODE ###

N, M = [int(i) for i in input().strip().split()]
A = [int(i) for i in input().strip().split()]
A.sort()

BC = [[0, 0] for _ in range(M)]
for j in range(M):
    BC[j][0], BC[j][1] = [int(i) for i in input().strip().split()]
BC.sort(key=lambda x: x[1])

res = 0
cnt = 0
i = N - 1
j = M - 1
while True:
    if cnt == N:
        break

    if j == -1:
        res += A[i]
        i -= 1
    elif A[i] > BC[j][1]:
        res += A[i]
        i -= 1
    elif A[i] <= BC[j][1]:
        res += BC[j][1]
        BC[j][0] -= 1
        if BC[j][0] == 0:
            j -= 1
    else:
        raise ValueError
    cnt += 1
print(res)
### BUGGY CODE ###

n = int(input())
a= list(map(int,input().split())) 
 
if 0 in a:
    print(0)
    quit()
 
ans = 1
for i in a:
    ans *= i 
    
    if ans > 1000000000000000000:
        ans = -1
    

print(ans)
    


### FIXED CODE ###

# import sys 
# input = sys.stdin.readline
 
 
n = int(input())
 
a= list(map(int,input().split())) 
 
def main(a):
    if 0 in a:
        print(0)
        return
     
    ans = 1
    for i in a:
        ans *= i 
        
        if ans > 1000000000000000000:
            print(-1)
            return
    
    print(ans)
    
main(a)
### BUGGY CODE ###

import copy
H,W,K=map(int,input().split())
S=[]
for _ in range(H):
    S.append([int(x) for x in list(input())])

ans=(H-1)+(W-1)

for i in range(2**(H-1)):
    check=[0]*H
    for j in range(H-1):
        if ((i>>j)&1):
            check[j+1]=check[j]+1
        else:
            check[j+1]=check[j]
    
    g=check[H-1]+1
    A=[0]*g
    c=0
    f=0
    for j in range(W):
        B=[0]*g
        for k in range(H):
            if S[k][j]==1:
                B[check[k]]+=1
            if B[check[k]]>K:
                c=10**4
                f=1
                break
        #print("AB",A,B)
        for l in range(g):
            if A[l]+B[l]>K:
                c+=1
                A=copy.copy(B)
                break
            else:
                A[l]+=B[l]
        if f:
            break
    ans=min(ans,c+g-1)

print(ans)




### FIXED CODE ###

import copy
H,W,K=map(int,input().split())
S=[]
for _ in range(H):
    S.append([int(x) for x in list(input())])

ans=(H-1)+(W-1)

for i in range(2**(H-1)):
    check=[0]*H
    for j in range(H-1):
        if ((i>>j)&1):
            check[j+1]=check[j]+1
        else:
            check[j+1]=check[j]
    
    g=check[H-1]+1
    A=[0]*g
    c=0
    f=0
    for j in range(W):
        B=[0]*g
        for k in range(H):
            if S[k][j]==1:
                B[check[k]]+=1
            if B[check[k]]>K:
                c=10**4
                f=1
                break
        if f:
            break
        #print("AB",A,B)
        for l in range(g):
            if A[l]+B[l]>K:
                c+=1
                A=copy.copy(B)
                break
            else:
                A[l]+=B[l]
    ans=min(ans,c+g-1)

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

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

from bisect import bisect_left
	
def LIS(L) :
    step = 0
    x = 0
    while True :
        for i in range(x, N) :
            if L[i] >= 0 :
                break
        else :
            break
            
        lis = [L[i]]
        pos = [i]
        x = i
        for p in range(i+1, N) :
            a = L[p]
            if a > lis[-1] :
                lis.append(a)
                pos.append(p)
            elif a >= 0 :
                s = bisect_left(lis, a)
                if lis[s] != a :
                    lis[s] = a
                    pos[s] = p
        # print(pos)
        for p in pos :
            L[p] = -1
        # print(L)
        step += 1
    return step

print(LIS(A))

### FIXED CODE ###

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

from bisect import bisect_right
	
def LIS(L) :   
    lis = [L[0]]
    for a in L[1:] :
        if a >= lis[-1] :
            lis.append(a)
        else :
            s = bisect_right(lis, a)
            lis[s] = a
    return len(lis)

print(LIS(A[::-1]))
### BUGGY CODE ###

MOD = 10 ** 9 + 7
ans = 1

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

#全部取る
if n == k:
    for x in a:
        ans *= x
    print(ans % MOD)

#全部負かつ奇数個取る
elif max(a) < 0 and k % 2:
    a.sort()
    for i in range(1, k+1):
        ans *= a[-i]
    print(ans % MOD)

else:
    pos = []
    neg = []
    
    for x in a:
        if x >= 0:
            pos.append(x)
        else:
            neg.append(x)
    
    pos.sort(reverse=True)
    neg.sort()
    

    if k % 2:
        ans *= pos.pop(0)
        k -= 1
    
    l = []
    
    for i in range(1, len(pos), 2):
        l.append(pos[i] * pos[i - 1])
    
    for i in range(1, len(neg), 2):
        l.append(neg[i] * neg[i - 1])
    
    l.sort(reverse=True)
    
    for i in range(k // 2):
        ans *= l[i]
        ans %= MOD
    
    print(ans % MOD)
    

### FIXED CODE ###

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

MOD = 10 ** 9 + 7
ans = 1

#全部取る
if n == k:
    for x in a:
        ans *= x
        ans %= MOD
    print(ans % MOD)

#全部負かつ奇数個取る
elif max(a) < 0 and k % 2:
    a.sort()
    for i in range(1, k+1):
        ans *= a[-i]
        ans %= MOD
    print(ans % MOD)

else:
    pos = []
    neg = []
    
    for x in a:
        if x >= 0:
            pos.append(x)
        else:
            neg.append(x)
    
    pos.sort(reverse=True)
    neg.sort()
    
    
    if k % 2:
        ans *= pos.pop(0)
        k -= 1
     
    #2個ずつ取る
    num = []
    for x, y in zip(pos[::2], pos[1::2]):
        num.append(x * y)
    for x, y in zip(neg[::2], neg[1::2]):
        num.append(x * y)

    num.sort(reverse=True)

    for i in range(k // 2):
        ans *= num[i]
        ans %= MOD
    
    print(ans % MOD)
### BUGGY CODE ###

n, a, b, c = map(int, input().split())
mod = 10 ** 9 + 7

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

an = n
bn = n
for i in range(n):
    an = an * a % mod
    an = an * (a + b) % mod
    bn = bn * b % mod
    bn = bn * (a + b) % mod
sum_a = an
sum_b = bn
for i in range(1, n):
    an = an * (n + i) % mod
    an = an * mod_inv(i, mod) % mod
    an = an * b % mod
    an = an * mod_inv(a + b, mod) % mod
    bn = bn * (n + i) % mod
    bn = bn * mod_inv(i, mod) % mod
    bn = bn * a % mod
    bn = bn * mod_inv(a + b, mod) % mod
    sum_a += an
    sum_b += bn
total = (sum_a + sum_b) * 100
q = 1
for i in range(2 * n):
    q = q * (a + b) % mod
q *= (100 - c)
print(total * mod_inv(q, mod) % mod)

### FIXED CODE ###

n, a, b, c = map(int, input().split())
mod = 10 ** 9 + 7

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

an = n
bn = n
for i in range(n):
    an *= a
    an *= (a + b)
    an %= mod
    bn *= b
    bn *= (a + b)
    bn %= mod
sum_a = an
sum_b = bn
inv_ab = mod_inv(a + b, mod)
for i in range(1, n):
    an *= (n + i)
    an *= mod_inv(i, mod)
    an *= b
    an *= inv_ab
    an %= mod
    bn *= (n + i)
    bn *= mod_inv(i, mod)
    bn *= a
    bn *= inv_ab
    bn %= mod
    sum_a += an
    sum_b += bn
total = (sum_a + sum_b) * 100
q = 1
for i in range(2 * n):
    q *= (a + b)
    q %= mod
q *= (100 - c)
print(total * mod_inv(q, mod) % mod)
### BUGGY CODE ###

def gud(a,b):
  if a%b==0:
    return b
  else:
    return gud(b,a%b)
a=int(input())
ans=0
for i in range(a):
  for j in range(a):
    n=gud(i+1,j+1)
    for k in range(a):
      ans+=gud(n,k+1)
print(ans)

### FIXED CODE ###

import math
def gud(a,b):
  if a%b==0:
    return b
  else:
    return gud(b,a%b)
a=int(input())
ans=0
for i in range(1,a+1):
  for j in range(1,a+1):
    n=math.gcd(i,j)
    for k in range(1,a+1):
      ans+=math.gcd(n,k)
print(ans)
### BUGGY CODE ###

def solve(N,X):
    ans = []
    cnt = X.count("1")

    for i in range(N):
        if X[i] == "1":
            X[i] = "0"
            ans.append(cal(X,cnt-1,0))
            X[i] = "1"
        else:
            X[i] = "1"
            ans.append(cal(X,cnt+1,0))
            X[i] = "0"

    return ans

def cal(X,cnt,rec):
    if cnt == 0:
        return rec
    else:
        amari = 0
        for i in range(len(X)):
            if X[i] == "1":
                amari += pow(2,len(X)-i-1,cnt)
                amari %= cnt
        b = bin(amari)[2:]
        Y = [b[i] for i in range(len(b))]
        cnt = Y.count("1")
        return cal(Y,cnt,rec+1)

def main():
    N = int(input())
    X = list(input())

    ans = solve(N,X)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()


### FIXED CODE ###

def solve(N,X):
    ans = []
    cnt = X.count("1")
    rem_ori = [0,0]
    for i in range(N):
        if X[i] == "1":
            if cnt != 1:
                rem_ori[0] += pow(2,N-i-1,cnt-1)
                rem_ori[0] %= (cnt-1)
            else:
                rem_ori[0] = 0
            rem_ori[1] += pow(2,N-i-1,cnt+1)
            rem_ori[1] %= (cnt+1)

    rem = [(rem_ori[0] if X[i] == "1" else rem_ori[1]) for i in range(N)]
    for i in range(N):
        if X[i] == "1":
            if cnt != 1:
                rem[i] -= pow(2,N-i-1,cnt-1)
                rem[i] %= (cnt-1)
                ans.append(cal(rem[i],1))
            else:
                ans.append(0)
        else:
            rem[i] += pow(2,N-i-1,cnt+1)
            rem[i] %= (cnt+1)
            ans.append(cal(rem[i],1))

    return ans

def cal(rem,rec):
    if rem == 0:
        return rec
    else:
        b = bin(rem)[2:]
        cnt = b.count("1")
        rem %= cnt
        return cal(rem,rec+1)

def main():
    N = int(input())
    X = input()

    ans = solve(N,X)
    for i in range(N):
        print(ans[i])

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

class BIT(object):
    def __init__(self, N, init=0, mod=1):
        self.N = N
        self.bit = [init for _ in range(N)]
        self.mod = mod

    def add(self, k, w):
        x = k
        while x < self.N:
            self.bit[x] += w % self.mod
            self.bit[x] %= self.mod
            x |= x + 1

    def sum(self, k):
        s = 0
        x = k - 1
        while x >= 0:
            s += self.bit[x]
            s %= self.mod
            x = (x & (x + 1)) - 1
        return s

MOD = 998244353
n, k = map(int, input().split())
seg = [list(map(int, input().split())) for _ in range(k)]
bit = BIT(n, mod=MOD)
bit.add(0, 1)

for i in range(1, n):
    x = 0
    for l, r in seg:
        x += (bit.sum(max(0, i - l + 1)) - bit.sum(max(0, i - r))) % MOD
        x %= MOD
    bit.add(i, x)
print((bit.sum(n) - bit.sum(n - 1)) % MOD)


### FIXED CODE ###

class BIT(object):
    def __init__(self, N, init=0, mod=1):
        self.N = N
        self.bit = [init for _ in range(N)]
        self.mod = mod

    def add(self, k, w):
        x = k
        while x < self.N:
            self.bit[x] += w % self.mod
            self.bit[x] %= self.mod
            x |= x + 1

    def sum(self, k):
        s = 0
        x = k - 1
        while x >= 0:
            s += self.bit[x]
            s %= self.mod
            x = (x & (x + 1)) - 1
        return s

MOD = 998244353
n, k = map(int, input().split())
seg = [list(map(int, input().split())) for _ in range(k)]
bit = BIT(n, mod=MOD)
bit.add(0, 1)

for i in range(1, n):
    x = 0
    for l, r in seg:
        x += (bit.sum(max(0, i - l + 1)) - bit.sum(max(0, i - r))) % MOD
        x %= MOD
    bit.add(i, x)
print((bit.sum(n) - bit.sum(n - 1)) % MOD)