output_description: Print the sum of the answers to the questions for the integers between 0 and X
  (inclusive), modulo 998244353.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      X
attempt: import sys
  
  input = sys.stdin.readline
  
  mod = 998244353
  
  N = int(input())
  X = input()
  
  import math
  
  xr = math.ceil(math.sqrt(N))
  
  LIST = []
  for i in range(1, xr + 1):
      if N % i == 0:
          LIST.append(i)
          LIST.append(N // i)
  
  REP = [l for l in set(LIST) if (N // l) % 2 == 1 and l != N]
  
  REP.sort(reverse=True)
  
  
  ANS = 2 * N * (int(X, 2) + 1) % mod
  
  
  def invstr(X, r):
      return bin(int(X, 2) ^ ((1 << r) - 1))[2:].zfill(r)
  
  
  from collections import defaultdict
  
  score = defaultdict(int)
  
  for r in REP:
      score[r] += 2 * r - 2 * N
  
      for j in REP:
          if r % j == 0 and j < r:
              score[j] -= score[r]
  
  for r in REP:
      sc = score[r]
  
      # print(r,score)
  
      XSTR = X[:r]
  
      kosuu = int(XSTR, 2)
  
      if (XSTR + invstr(XSTR, r)) * (N // (r * 2)) + XSTR <= X:
          kosuu += 1
  
      ANS += kosuu * sc
  
  print(ANS % mod)
  
problem_description: Statement
  
  Given are integers N and X. For each integer k between 0 and X (inclusive),
  find the answer to the following question, then compute the sum of all those
  answers, modulo 998244353.
  
    * Let us repeat the following operation on the integer k. Operation: if the integer is currently odd, subtract 1 from it and divide it by 2; otherwise, divide it by 2 and add 2^{N-1} to it. How many operations need to be performed until k returns to its original value? (The answer is considered to be 0 if k never returns to its original value.)
samples: [{"input": "3\n    111", "output": "40\n    \n\nFor example, for k=3, the operation changes k as follows: 1,0,4,6,7,3.\nTherefore the answer for k=3 is 6.\n\n* * *"}, {"input": "6\n    110101", "output": "616\n    \n\n* * *"}, {"input": "30\n    001110011011011101010111011100", "output": "549320998"}]