output_description: Print x_{N,1}.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      a_1a_2\ldotsa_N
attempt: import math
  
  N = int(input())
  a = input()
  
  u = int(math.sqrt(N))
  u2 = int(math.sqrt(u))
  dic = {}
  dic2 = {}
  
  
  def calc(s: str) -> int:
      dp = [[0] * len(s) for i in range(len(s))]
      for i in range(len(s)):
          for j in range(len(s) - i):
              if i == 0:
                  dp[i][j] = int(s[j])
              else:
                  dp[i][j] = abs(dp[i - 1][j] - dp[i - 1][j + 1])
      return dp[len(s) - 1][0]
  
  
  preva = a
  for i in range(1, N // u):
      preva_list = []
      for j in range(N - (u - 1)):
          s = preva[j : j + u]
          ans = 0
  
          if s in dic:
              ans = dic[s]
          else:
              # ans = calc(s)
              # dic[s] = ans
  
              # print('s: ', s)
              preva2 = s
              for i2 in range(1, u // u2):
                  preva2_list = []
                  for j2 in range(len(s) - (u2 - 1)):
                      s2 = preva2[j2 : j2 + u2]
                      ans2 = 0
                      if s2 in dic2:
                          ans2 = dic2[s2]
                      else:
                          ans2 = calc(s2)
                          dic2[s2] = ans2
                      preva2_list.append(str(ans2))
                      # print('s2: ', s2)
                      # print('ans2: ', ans2)
                  preva2 = "".join(preva2_list)
              ans = calc(preva2)
              dic[s] = ans
              # print('ans: ', ans)
  
          preva_list.append(str(ans))
      preva = "".join(preva_list)
  
  ans = calc(preva)
  print(ans)
  
problem_description: Statement
  
  Given is a sequence of N digits a_1a_2\ldots a_N, where each element is 1, 2,
  or 3. Let x_{i,j} defined as follows:
  
    * x_{1,j} := a_j \quad (1 \leq j \leq N)
    * x_{i,j} := | x_{i-1,j} - x_{i-1,j+1} | \quad (2 \leq i \leq N and 1 \leq j \leq N+1-i)
  
  Find x_{N,1}.
samples: [{"input": "4\n    1231", "output": "1\n    \n\nx_{1,1},x_{1,2},x_{1,3},x_{1,4} are respectively 1,2,3,1.\n\nx_{2,1},x_{2,2},x_{2,3} are respectively |1-2| = 1,|2-3| = 1,|3-1| = 2.\n\nx_{3,1},x_{3,2} are respectively |1-1| = 0,|1-2| = 1.\n\nFinally, x_{4,1} = |0-1| = 1, so the answer is 1.\n\n* * *"}, {"input": "10\n    2311312312", "output": "0"}]