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

import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [-i for i in a]
heapq.heapify(a)
for i in range(m):
    c = heapq.heappop(a)
    c = -c // 2
    heapq.heappush(a, -c)
    if sum(a) == 0:
        break
print(-sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [-i for i in a]
heapq.heapify(a)
for i in range(m):
    c = heapq.heappop(a)
    c = -c // 2
    heapq.heappush(a, -c)
    if a[0] == 0:
        break
print(-sum(a))
### BUGGY CODE ###

from collections import defaultdict as ddic, deque
from itertools import combinations, permutations, product
import sys
sys.setrecursionlimit(10**6)
stdout = sys.stdout
rr = lambda: raw_input().strip()
rri = lambda: int(raw_input())
rrm = lambda: list(map(int, raw_input().strip().split()))


def solve(N, A):
    memo = {}
    def dp(i, color):
        if i == N: return 0
        if (i, color) in memo:
            return memo[i, color]
        if color == 1:  # black
            # no white
            ans = dp(i+1, 1) + (A[i] != color)
        else:
            ans = min(dp(i+1, 0), dp(i+1, 1)) + (A[i] != color)
        memo[i, color] = ans
        return ans

    return min(dp(0, 0), dp(0, 1))
###
N = rri()
S = rr()
A = [1 if c == '#' else 0 for c in S]
print solve(N, A)


### FIXED CODE ###

from collections import defaultdict as ddic, deque
from itertools import combinations, permutations, product
import sys
sys.setrecursionlimit(10**6)
stdout = sys.stdout
rr = lambda: raw_input().strip()
rri = lambda: int(raw_input())
rrm = lambda: list(map(int, raw_input().strip().split()))


def solve(N, A):
    dp0 = [0] * (N+1)
    dp1 = [0] * (N+1)
    for i in xrange(N-1, -1, -1):
        for color in (0, 1):
            if color == 1:
                ans = dp1[i+1] + (A[i] != color)
            else:
                ans = min(dp0[i+1], dp1[i+1]) + (A[i] != color)

            if color == 0:
                dp0[i] = ans
            else:
                dp1[i] = ans

    return min(dp0[0], dp1[0])

###
N = rri()
S = rr()
A = [1 if c == '#' else 0 for c in S]
print solve(N, A)
### BUGGY CODE ###

import collections
n=int(input())
a=list(map(int, input().split(' ')))
c = collections.Counter(a)

def n_c_2(val):
  ret = 0
  if val > 1:
    ret = (val)*(val-1)//2
  return ret

org_nc2 = {}
org_minus1_nc2 = {}
ans = {}

for k in list(c.keys()):
  org_nc2[k] = n_c_2(c[k])
for k in list(c.keys()):
  org_minus1_nc2[k] = n_c_2(c[k] - 1)
for k in list(c.keys()):
  tmp = 0
  for j in list(c.keys()):
    if j==k:
      tmp += org_minus1_nc2[j]
    else:
      tmp += org_nc2[j]
  ans[k] = tmp

for d in a:
  print (ans[d])


### FIXED CODE ###

import collections
n=int(input())
a=list(map(int, input().split(' ')))
c = collections.Counter(a)

def n_c_2(val):
  ret = 0
  if val > 1:
    ret = (val)*(val-1)//2
  return ret

org_nc2 = {}
org_minus1_nc2 = {}
sumall = 0
for k in list(c.keys()):
  org_nc2[k] = n_c_2(c[k])
  org_minus1_nc2[k] = n_c_2(c[k] - 1)
  sumall += org_nc2[k]
for d in a:
  ans = sumall - org_nc2[d] + org_minus1_nc2[d]
  print (ans)
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
ans = 0
d = [0]
max_i = 0
t = 0
for i in range(len(p)):
  d.append(d[-1]+p[i])
  if i < k: continue
  if d[i+1]-d[i-k+1] > t:
    t = d[i+1]-d[i-k+1]
    max_i = i-k+1
ans = sum([sum(range(i+1))/i for i in p[max_i:max_i+k]])
print(ans)



### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
p_ = [(i+1)/2 for i in p]
d = [0]
for i in p_:
  d.append(d[-1]+i)
ans = 0
for i in range(k,n+1):
  if ans < d[i]-d[i-k]:
    ans = d[i]-d[i-k]
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
cnt = 0
ans = []

for i in range(n):
    cnt += 1
    ind = a.index(cnt)
    ans.append(str(ind + 1))

print(" ".join(ans))
    
    

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
cnt = 0
ans = [0] * n

for i in a:
    cnt += 1
    ans[i-1] = str(cnt)

print(" ".join(ans))
### BUGGY CODE ###

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

ans = 0
for i in range(N-1):
  s = 0
  for j in range(i+1, N):
    s += A[j]
    s %= (10**9)+7
  tmp = A[i]*s
  tmp %= (10**9)+7
  ans += tmp
  ans %= (10**9)+7
print(ans)

### FIXED CODE ###

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

left = A[0]
left %= (10**9)+7
right = sum(A) - A[0]
right %= (10**9)+7
ans = 0
for i in range(1, N):
  tmp = left * right
  tmp %= (10**9)+7
  ans += tmp
  ans %= (10**9)+7
  left = A[i]
  right -= A[i]
print(ans)
### BUGGY CODE ###

import collections

n = int(input())
s = []

for _ in range(n):
  s.append(collections.Counter(input()))

count = 0

for i in range(n):
  for j in range(i+1, n):
    if s[i] == s[j]:
      count += 1
      
print(count)

### FIXED CODE ###

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

for _ in range(n):
  value = input()
  key = ''.join(sorted(value))
  
  if key in s:
    s[key] += 1
  else:
    s[key] = 1
          
sum = 0

for value in s.values():
  sum += value*(value-1)//2
  
print(sum)
### BUGGY CODE ###

from collections import Counter

n = int(input())
d = list(map(int, input().split()))

count = Counter(d)

if d[0] != 0:
    print(0)
    


#print(count[0])
#print(len(count))
#print(count.keys())
#print(count.items())
elif count[0] != 1:
    print(0)
    
else:
    ans = 1
    tmp = 1
    for i in range(1, len(d)+1):
        
        ans *= tmp**count[i]
        #print(ans)
        tmp = count[i]


    print(ans%998244353)



### FIXED CODE ###

from collections import Counter

n = int(input())
d = list(map(int, input().split()))

count = Counter(d)

if d[0] != 0:
    print(0)
    


#print(count[0])
#print(len(count))
#print(count.keys())
#print(count.items())
elif count[0] != 1:
    print(0)
    
else:
    ans = 1
    tmp = 1
    max_d = max(d)
    for i in range(1, max_d+1):
        
        ans *= tmp**count[i]
        #print(ans)
        tmp = count[i]


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

n,a,b=map(int,input().split())
s=[]
ans=0
for i in range(n):
  h=int(input())
  s.append(h)
while max(s)>0:
  ans+=1
  s.sort()
  s[-1]-=a-b
  for i in range(n):
    s[i]-=b
print(ans)

### FIXED CODE ###

_,a,b,*H=map(int,open(0).read().split())
l,r=0,10**9
while r-l>1:
	m=(l+r)//2
	if-sum(min(0,(h-m*b)//(b-a))for h in H)>m:l=m
	else:r=m
print(r)
### BUGGY CODE ###

import math

A,B,Q = map(int, input().split())
S=[0]*A
T=[0]*B
for i in range(A):
  S[i] = int(input())
for i in range(B):
  T[i] = int(input())
S.append(10**11)
S.insert(0,(-1)*(10**11))
T.append(10**11)
T.insert(0,(-1)*(10**11))
for i in range(Q):
  x = int(input())
  floor = 0
  ceil = len(S)-1
  while ceil-floor > 1:
    half = math.floor((floor+ceil)/2)
    s = S[half]
    if s < x:
      floor = half
    else:
      ceil = half
  nearest_x_S = [S[floor]-x, S[ceil]-x]
        
  floor = 0
  ceil = len(T)-1
  while ceil-floor > 1:
    half = math.floor((floor+ceil)/2)
    t = T[half]
    if t < x:
      floor = half
    else:
      ceil = half
  nearest_x_T = [T[floor]-x, T[ceil]-x]
  
  ans_cand = []
  for x_S in nearest_x_S:
    for x_T in nearest_x_T:
      if x_S*x_T > 0:
        ans_cand.append(max(abs(x_S),abs(x_T)))
      else:
        ans_cand.append(abs(x_S)+abs(x_T)+min(abs(x_S),abs(x_T)))
  print(int(min(ans_cand)))

### FIXED CODE ###

mod = 1000000007
eps = 10**-9
inf = 10**15


def main():
    import sys
    from bisect import bisect_left
    input = sys.stdin.buffer.readline

    A, B, Q = map(int, input().split())
    S = [-inf]
    for _ in range(A):
        S.append(int(input()))
    S.append(inf)
    T = [-inf]
    for _ in range(B):
        T.append(int(input()))
    T.append(inf)

    for _ in range(Q):
        x = int(input())
        i = bisect_left(S, x)
        j = bisect_left(T, x)
        ans = []
        ans.append(x - S[i-1] + abs(S[i-1] - T[j-1]))
        ans.append(x - S[i-1] + abs(S[i-1] - T[j]))
        ans.append(x - T[j-1] + abs(T[j-1] - S[i-1]))
        ans.append(x - T[j-1] + abs(T[j-1] - S[i]))
        ans.append(S[i] - x + abs(S[i] - T[j-1]))
        ans.append(S[i] - x + abs(S[i] - T[j]))
        ans.append(T[j] - x + abs(T[j] - S[i-1]))
        ans.append(T[j] - x + abs(T[j] - S[i]))
        print(min(ans))


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

n = int(input())
sunuke = 1
for i in range(1, n+1):
  sunuke = sunuke * i

print(sunuke % 1000000007)


### FIXED CODE ###

n = int(input())
sunuke = 1
for i in range(1, n+1):
  sunuke = sunuke * i % 1000000007

print(sunuke)
### BUGGY CODE ###

import collections, sys
N, P = map(int, input().split())
S = input()
s_mod = [0]*(N+1)

ans = 0
if P == 2:
    for i in range(N):
        ans += ((int(S[-(i+1)])%2) ^ 1) * (N-i)
    print(ans)
    sys.exit()
elif P == 5:
    for i in range(N):
        ans += ((int(S[-(i + 1)]) % 5)==0) * (N - i)
    print(ans)
    sys.exit()


for i in range(N):
    s_mod[i+1] = (10**i*int(S[-(i+1)])+s_mod[i]) % P
c = collections.Counter(s_mod)
for v in c.values():
    ans = (ans + v*(v-1)//2)
print(ans)


### FIXED CODE ###

import collections, sys
N, P = map(int, input().split())
S = input()
s_mod = [0]*(N+1)

ans = 0
if P == 2:
    for i in range(N):
        ans += ((int(S[-(i+1)])%2) ^ 1) * (N-i)
    print(ans)
    sys.exit()
elif P == 5:
    for i in range(N):
        ans += ((int(S[-(i + 1)]) % 5) == 0) * (N - i)
    print(ans)
    sys.exit()


for i in range(N):
    s_mod[i+1] = (pow(10, i, P) * int(S[-(i+1)])+s_mod[i]) % P
c = collections.Counter(s_mod)
for v in c.values():
    ans = (ans + v*(v-1)//2)
print(ans)
### BUGGY CODE ###

def hantei(n, m, l, d ):
    if (n*10000+m*5000+l*1000)==d:
        return True
    return False

osatu,sum = map(int,input().split())

#n　一万円
#m　五千円
#l　千円
n=m=l=0
result=0

while(n <= osatu):
    while(m <= osatu):
        while(l <= osatu):
            if n+m+l < osatu:
                pass
            elif n+m+l == osatu:
                if hantei(n,m,l,sum)==True:
                    print(n,m,l)
                    exit (0)            
            else:
                break
            l+=1
        l=0
        if n+m+l<=osatu:
            m+=1
        else:
            break
    m=l=0
    n+=1


print("-1 -1 -1")




### FIXED CODE ###

def hantei(n, m, l, d ):
    if (n*10000+m*5000+l*1000)==d:
        return True
    return False

osatu,sum = map(int,input().split())

#n　一万円
#m　五千円
#l　千円
n=m=l=0
result=0

while(n <= osatu):
    while(m+n <= osatu):
        l=osatu-n-m
        if n+m+l==osatu:
            if hantei(n,m,l,sum)==True:
                print(n,m,l)
                exit (0)
        m+=1
    m=0
    n+=1


print("-1 -1 -1")
### BUGGY CODE ###

import heapq

N,M=map(int,input().split())
A=list(map(int,input().split()))
heapq.heapify(A)
for _ in range(M):
  b,c=map(int,input().split())
  for _ in range(b):
    a=heapq.heappop(A)
    if c>a:
      heapq.heappush(A,c)
    else:
      heapq.heappush(A,a)
      break
print(sum(A))

### FIXED CODE ###

N,M=map(int,input().split())
A=map(int,input().split())
L=[(1,a) for a in A]
for _ in range(M):
  b,c=map(int,input().split())
  L.append((b,c))
L=sorted(L,key=lambda x: x[1],reverse=True)
ans,k=0,0
for n,a in L:
  if n+k>=N:
    ans+=a*(N-k)
    break
  else:
    ans+=a*n
    k+=n
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
A = [int(input()) for i in range(N)]
c = collections.Counter(A)
ans = 0
for i in range(len(c)):
    ans += c.most_common()[i][1] % 2
print(ans)

### FIXED CODE ###

import collections
N = int(input())
A = [int(input()) for i in range(N)]
c = collections.Counter(A).most_common()
ans = 0
for i in range(len(c)):
    ans += c[i][1] % 2
print(ans)
### BUGGY CODE ###

import math
n = int(input())
sum = 1

if n % 2 == 1:
    print(0)
else:
    n = math.factorial(n//2)
    count = 0
    while n % 5 == 0:
        count+=1
        n//=5
    print(count)

### FIXED CODE ###

n = int(input())

if n % 2 == 1:
    print(0)
else:
    count = 0
    n=n//2
    while n // 5 != 0:
        count += n // 5
        n//=5
    print(count)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
    max_idx = a.index(max(a))
    a[max_idx] = a[max_idx] // 2
print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = list(map(lambda x: x*-1, a))
heapq.heapify(a)
for i in range(m):
    tar = heapq.heappop(a)
    ins = ((tar*-1) // 2)*-1
    heapq.heappush(a, ins)
a = list(map(lambda x: x*-1, a))
print(sum(a))
### BUGGY CODE ###

import queue
import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
XYZ = []
for _ in range(M):
    XYZ.append(tuple(map(int, input().split())))

G=[[] for _ in range(N+1)]
for el in XYZ:
    G[el[0]].append(el[1])
    G[el[1]].append(el[0])
#print(G)

tosee = set()
for i in range(1,N+1):
    tosee.add(i)
#print(tosee)
todo=queue.Queue()
def dfs(n):
    if n in tosee:
        tosee.remove(n)
    for nxt in G[n]:
        if nxt in tosee:
            todo.put(nxt)
    if todo.empty():
        return None
    else:
        dfs(todo.get())


cnt=0
while tosee:
    cnt+=1
    dfs(tosee.pop())
print(cnt)


### FIXED CODE ###

import queue
import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
XYZ = []
for _ in range(M):
    XYZ.append(tuple(map(int, input().split())))

G=[[] for _ in range(N+1)]
for el in XYZ:
    G[el[0]].append(el[1])
    G[el[1]].append(el[0])
#print(G)

seen=[False]*(N+1)
todo=queue.Queue()
def bfs(n):
    seen[n]=True
    for nxt in G[n]:
        if seen[nxt]==False:
            bfs(nxt)


cnt=0
for check in range(1, N+1):
    if seen[check]==False:
        cnt+=1
        bfs(check)
print(cnt)
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
count = 0
max_i = 0
H.append(10**9 + 2)
for i in range(N):
  if H[i] > H[i + 1] + 1:
    count += 1
  if max_i - H[i] > 1:
    count += 1
  max_i = max(H[:i+1])

    
if count == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
count = 0
max_i = 0
H.append(10**9 + 2)
for i in range(N):
  if H[i] > H[i + 1] + 1:
    count += 1
  if max_i - H[i] > 1:
    count += 1
  max_i = max(max_i,H[i])

    
if count == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

# 2019-11-14 10:01:24(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

mod = 10 ** 9 + 7
def main():
    n, m, *broken_treads = [int(x) for x in sys.stdin.read().split()]
    safe = sorted((set(range(1, n+1)) - set(broken_treads)))

    ans = 1
    p_pre_pre = 0
    p_pre = 1 # 0th step
    count = 0
    continuous_broken_count = 0
    for i in range(1, n+1):
        if i in safe:
            continuous_broken_count = 0
            count += 1
            if count % 2 == 1:
                p_pre_pre = p_pre + p_pre_pre
            else:
                p_pre = p_pre_pre + p_pre
        elif count != 0:
            continuous_broken_count = 1
            if count % 2 == 1:
                ans = ans * p_pre_pre % mod
            else:
                ans = ans * p_pre % mod
            p_pre_pre = 1
            p_pre = 0
            count = 0
        else:
            continuous_broken_count += 1
            if continuous_broken_count == 2:
                print(0)
                sys.exit()
            p_pre_pre = 1    
            p_pre = 0

    if count != 0:      # if n-th tread is not broken.
        if count % 2 == 1:
            ans = ans * p_pre_pre % mod
        else:
            ans = ans * p_pre % mod

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

mod = 10 ** 9 + 7
n, m, *a = [int(x) for x in sys.stdin.read().split()]

safe = sorted(set(range(1,n+1)) - set(a))
dp = [0] * (n + 2)
dp[0] = 0
dp[1] = 1
for i in safe:
    dp[i+1] = (dp[i] + dp[i-1]) % mod

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

import itertools

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

comb = itertools.combinations(s,2)

cnt = 0
for x,y in comb:
  x = list(x)
  x.sort()
  y = list(y)
  y.sort()
  if x == y:
    cnt += 1

print(cnt)

### FIXED CODE ###

from collections import Counter
from math import factorial

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

for i in range(N):
  s[i] = list(s[i])
  s[i].sort()
  s[i] = "".join(s[i])
  
x = Counter(s).most_common()
cnt = 0
for i in range(len(x)):
  if x[i][1] >1:
    cnt += factorial(x[i][1]) // 2 // factorial(x[i][1] -2)
print(cnt)
### BUGGY CODE ###

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n = int(input())
a = list(map(int, input().split()))
a_sorted = sorted(a)
d = []
e = []
f = []
for i in range(n-1):
    b = a_sorted[i+1]
    for c in a_sorted:
        if c <  b:
            e.append(b)
            f.append(c)
            d.append(combinations_count(b,c))
g = d.index(max(d))
print('%d %d'%(e[g],f[g]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
# kakomon toku
import math
import sys
import itertools
import numpy as np
 
n = int(input())
a = [int(i) for i in input().split()]
 
#print(a)
a = np.sort(a)
ai = a[n-1]
aj = a[0]
center = ai / 2
diff = ai
i=0
for m in a:
    if diff > abs(m - center) :
        aj = m
        diff = abs(aj - center)
    else:
        break
 
print(ai,aj)
### BUGGY CODE ###

import numpy as np
N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for i in range(M)]
 
AB.reverse()

reader = np.array([i + 1 for i in range(N)])
size = np.array([1 for i in range(N)])

def root(a):
  if reader[a-1] == a:
    return a - 1
  else:
    return reader[a-1] - 1

def merge(a, b):
  # calc root index
  a = root(a)
  b = root(b)
  if a == b:
    return 0
  res = size[a] * size[b]
  if size[a] >= size[b]:
    # add size is root
    size[a] += size[b]
    # replace zero is all child node
    size[b] = 0
    reader[reader == reader[b]] = reader[a]
  else:
    size[b] += size[a]
    size[a] = 0
    reader[reader == reader[a]] = reader[b]
  return res

result = []
ans = N * (N-1)/2
for i in AB:
  result.append(ans)
  ans -= merge(i[0], i[1])
for i in result[::-1]:
  print(int(i))

### FIXED CODE ###

from collections import Counter
# union find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

AB = AB[::-1]
ret = []
tmp = 0
uf = UnionFind(N)
for a,b in AB:
    if uf.is_same_group(a-1, b-1):
        ret.append(0)
    else:

        ret.append(uf.count(a-1) * uf.count(b-1))
        uf.unite(a-1,b-1)

ans = 0
for i in range(M-1, -1, -1):
    ans += ret[i]
    print(ans)
### BUGGY CODE ###

from fractions import gcd


def lcm(x, y):
    return x // gcd(x, y) * y


N = int(input())
A = list(map(int, input().split()))
_lcm = 1
for a in A:
    _lcm = lcm(_lcm, a)
ans = 0
for a in A:
    ans += _lcm // a
    ans %= 1000000007
print(ans)

### FIXED CODE ###

from fractions import gcd


def lcm(x, y):
    return x // gcd(x, y) * y


def extgcd(a, b):
    if b == 0:
        return [1, 0, a]
    x, y, g = extgcd(b, a % b)
    return [y, x - a//b * y, g]


def mod_inverse(a, m):
    x, y, _ = extgcd(a, m)
    return (m + x % m) % m


N = int(input())
A = list(map(int, input().split()))
_lcm = 1
for a in A:
    _lcm = lcm(_lcm, a)
ans = 0
for a in A:
    ans += _lcm * mod_inverse(a, 1000000007)
print(ans % 1000000007)
### BUGGY CODE ###

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

MOD = 10 ** 9 + 7

lst = [0] * 65
for a in A:
    tmp = a
    for i in range(61):
        lst[i] += tmp % 2
        tmp //= 2
        if tmp == 0:
            break

calc = [1]
for i in range(65):
    calc.append(calc[-1] * 2)

ans = 0
for a in A:
    tmp = a
    for i in range(61):
        n = tmp % 2
        tmp //= 2
        if n == 1:
            ans += calc[i] * (N - lst[i])
        else:
            ans += calc[i] * lst[i]
    ans %= MOD

def modinv(a, m): #mod m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u

# print (ans)
ans *= modinv(2, MOD)
print (ans % MOD)

### FIXED CODE ###

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

MOD = 10 ** 9 + 7

lst = [0] * 65
for a in A:
    tmp = a
    for i in range(61):
        lst[i] += tmp % 2
        tmp //= 2
        if tmp == 0:
            break

calc = [1]
for i in range(65):
    calc.append((calc[-1] * 2) % MOD)

ans = 0
for a in A:
    tmp = a
    for i in range(61):
        n = tmp % 2
        tmp //= 2
        if n == 1:
            ans += calc[i] * (N - lst[i])
        else:
            ans += calc[i] * lst[i]
    ans %= MOD

def modinv(a, m): #mod m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u

# print (ans)
ans *= modinv(2, MOD)
print (ans % MOD)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
lr = [list(map(int,input().split())) for _ in range(q)]

ac = [0]*n

for i in range(n-1):
  if s[i:i+2]=='AC':  
    ac[i]=1
    
for l,r in lr:
  print(sum(ac[l-1:r-1]))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
lr = [list(map(int,input().split())) for _ in range(q)]

ac = [0]*(n+1)

for i in range(1,n+1):
  if s[i-1:i+2-1]=='AC':  
    ac[i]=ac[i-1] + 1
  else:
    ac[i]=ac[i-1]
    
for l,r in lr:
  print(ac[r-1]-ac[l-1])
### BUGGY CODE ###

# E - Colorful Blocks
import sys
readline = sys.stdin.readline

MOD = 998244353
N, M, K = map(int, readline().split())

# 予め階乗を計算しておく
f = [1]
for i in range(N):
    f.append(f[i]*(i+1)%MOD)

# 組み合わせ関数
def comb_mod(n, r, p):
    return (f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p))%p

ans = 0
for i in range(K+1):
    ans = (ans + (M*pow(M-1, N-1-i, MOD)) * comb_mod(N-1, i, MOD))%MOD

print(ans)


### FIXED CODE ###

# E - Colorful Blocks

MOD = 998244353
N, M, K = map(int, input().split())

# 予め階乗を計算しておく
f = [1]
for i in range(N):
    f.append(f[i]*(i+1)%MOD)

# 組み合わせ関数
def comb_mod(n, r, p):
    return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p)

ans = 0
for i in range(K+1):
    ans = (ans + (M*pow(M-1, N-1-i,MOD)) * comb_mod(N-1, i, MOD))%MOD

print(ans)