





from __future__ import annotations

from collections.abc import Callable

_snake_case  :   Optional[Any]						   =  list[list[float | int]]

def   a_   (			lowerCAmelCase_				:      Matrix,     lowerCAmelCase_				:      Matrix     ):
   __lowerCAmelCase							     =     len(lowerCAmelCase_     )
   __lowerCAmelCase							     =     [[0 for _ in range(size + 1     )] for _ in range(lowerCAmelCase_     )]
   __lowerCAmelCase							     =     42
   __lowerCAmelCase							     =     42
   __lowerCAmelCase							     =     42
   __lowerCAmelCase							     =     42
   __lowerCAmelCase							     =     42
   __lowerCAmelCase							     =     42

   for row in range(lowerCAmelCase_     ):
      for col in range(lowerCAmelCase_     ):
         __lowerCAmelCase							     =     matrix[row][col]

      __lowerCAmelCase							     =     vector[row][0]

   __lowerCAmelCase							     =     0
   __lowerCAmelCase							     =     0
   while row < size and col < size:
      # pivoting
      __lowerCAmelCase							     =     max((abs(augmented[rowa][col]     ), rowa) for rowa in range(lowerCAmelCase_,     lowerCAmelCase_     )     )[
          1
      ]
      if augmented[pivot_row][col] == 0:
         col += 1
         continue
      else:
         __lowerCAmelCase     ,     __lowerCAmelCase							     =     augmented[pivot_row], augmented[row]

      for rowa in range(row + 1,     lowerCAmelCase_     ):
         __lowerCAmelCase							     =     augmented[rowa][col] / augmented[row][col]
         __lowerCAmelCase							     =     0
         for cola in range(col + 1,     size + 1     ):
            augmented[rowa][cola] -= augmented[row][cola] * ratio

      row += 1
      col += 1

   # back substitution
   for col in range(1,     lowerCAmelCase_     ):
      for row in range(lowerCAmelCase_     ):
         __lowerCAmelCase							     =     augmented[row][col] / augmented[col][col]
         for cola in range(lowerCAmelCase_,     size + 1     ):
            augmented[row][cola] -= augmented[col][cola] * ratio

    # round to get rid of numbers like 2.000000000000004
   return [
       [round(augmented[row][size] / augmented[row][row],     10     )] for row in range(lowerCAmelCase_     )
   ]

def   a_   (			lowerCAmelCase_				:      list[int]     ):
   __lowerCAmelCase							     =     len(lowerCAmelCase_     )
   __lowerCAmelCase							     =     [[0 for _ in range(lowerCAmelCase_     )] for _ in range(lowerCAmelCase_     )]
   __lowerCAmelCase							     =     [[0] for _ in range(lowerCAmelCase_     )]
   __lowerCAmelCase							     =     42
   __lowerCAmelCase							     =     42
   __lowerCAmelCase							     =     42
   __lowerCAmelCase							     =     42

   for x_val, y_val in enumerate(lowerCAmelCase_     ):
      for col in range(lowerCAmelCase_     ):
         __lowerCAmelCase							     =     (x_val + 1) ** (size - col - 1)
      __lowerCAmelCase							     =     y_val

   __lowerCAmelCase							     =     solve(lowerCAmelCase_,     lowerCAmelCase_     )

   def interpolated_func(lowerCAmelCase_				:      int     ) -> int:
      return sum(
          round(coeffs[x_val][0]     ) * (var ** (size - x_val - 1))
          for x_val in range(lowerCAmelCase_     )     )

   return interpolated_func

def   a_   (			lowerCAmelCase_				:      int     ):
   return (
       1
       - variable
       + variable**2
       - variable**3
       + variable**4
       - variable**5
       + variable**6
       - variable**7
       + variable**8
       - variable**9
       + variable**10
   )

def   a_   (			lowerCAmelCase_				:      Callable[[int], int] = question_function,     lowerCAmelCase_				:      int = 10     ):
   __lowerCAmelCase							     =     [func(lowerCAmelCase_     ) for x_val in range(1,     order + 1     )]

   __lowerCAmelCase							     =     [
       interpolate(data_points[:max_coeff]     ) for max_coeff in range(1,     order + 1     )
   ]

   __lowerCAmelCase							     =     0
   __lowerCAmelCase							     =     42
   __lowerCAmelCase							     =     42

   for poly in polynomials:
      __lowerCAmelCase							     =     1
      while func(lowerCAmelCase_     ) == poly(lowerCAmelCase_     ):
         x_val += 1

      ret += poly(lowerCAmelCase_     )

   return ret


if __name__ == "__main__":
     print(F"""{solution() = }""")








import mpmath  # for roots of unity
import numpy as np



class     _UpperCAmelCase   :

  """simple docstring"""


  def __init__(    self			:		List[Any] ,  lowerCAmelCase_			:		Dict=None ,  lowerCAmelCase_			:		str=None					)							->						List[Any]:
     # Input as list
     __lowerCAmelCase							     =     list(poly_a or [0]					)[:]
     __lowerCAmelCase							     =     list(poly_b or [0]					)[:]

     # Remove leading zero coefficients
     while self.polyA[-1] == 0:
        self.polyA.pop()
     __lowerCAmelCase							     =     len(self.polyA					)

     while self.polyB[-1] == 0:
        self.polyB.pop()
     __lowerCAmelCase							     =     len(self.polyB					)

     # Add 0 to make lengths equal a power of 2
     __lowerCAmelCase							     =     int(
         2 ** np.ceil(np.loga(len(self.polyA					) + len(self.polyB					) - 1					)					)					)

     while len(self.polyA					) < self.c_max_length:
        self.polyA.append(0					)
     while len(self.polyB					) < self.c_max_length:
        self.polyB.append(0					)
     # A complex root used for the fourier transform
     __lowerCAmelCase							     =     complex(mpmath.root(x=1 ,  n=self.c_max_length ,  k=1					)					)

     # The product
     __lowerCAmelCase							     =     self.__multiply()






  def     lowercase		(    self			:		Optional[int] ,  lowerCAmelCase_			:		str					)							->						Optional[int]:
     __lowerCAmelCase							     =     [[x] for x in self.polyA] if which == 'A' else [[x] for x in self.polyB]
     # Corner case
     if len(lowerCAmelCase_					) <= 1:
        return dft[0]
     #
     __lowerCAmelCase							     =     self.c_max_length // 2
     while next_ncol > 0:
        __lowerCAmelCase							     =     [[] for i in range(lowerCAmelCase_					)]
        __lowerCAmelCase							     =     self.root**next_ncol

        # First half of next step
        __lowerCAmelCase							     =     1
        for j in range(self.c_max_length // (next_ncol * 2)					):
           for i in range(lowerCAmelCase_					):
              new_dft[i].append(dft[i][j] + current_root * dft[i + next_ncol][j]					)
           current_root *= root
        # Second half of next step
        __lowerCAmelCase							     =     1
        for j in range(self.c_max_length // (next_ncol * 2)					):
           for i in range(lowerCAmelCase_					):
              new_dft[i].append(dft[i][j] - current_root * dft[i + next_ncol][j]					)
           current_root *= root
        # Update
        __lowerCAmelCase							     =     new_dft
        __lowerCAmelCase							     =     next_ncol // 2
     return dft[0]






  def     lowercase		(    self			:		Optional[int]					)							->						Any:
     __lowerCAmelCase							     =     self.__dft('A'					)
     __lowerCAmelCase							     =     self.__dft('B'					)
     __lowerCAmelCase							     =     [[dft_a[i] * dft_b[i] for i in range(self.c_max_length					)]]
     del dft_a
     del dft_b

     # Corner Case
     if len(inverce_c[0]					) <= 1:
        return inverce_c[0]
     # Inverse DFT
     __lowerCAmelCase							     =     2
     while next_ncol <= self.c_max_length:
        __lowerCAmelCase							     =     [[] for i in range(lowerCAmelCase_					)]
        __lowerCAmelCase							     =     self.root ** (next_ncol // 2)
        __lowerCAmelCase							     =     1
        # First half of next step
        for j in range(self.c_max_length // next_ncol					):
           for i in range(next_ncol // 2					):
              # Even positions
              new_inverse_c[i].append(
                  (
                      inverce_c[i][j]
                      + inverce_c[i][j + self.c_max_length // next_ncol]
                  )
                  / 2					)
              # Odd positions
              new_inverse_c[i + next_ncol // 2].append(
                  (
                      inverce_c[i][j]
                      - inverce_c[i][j + self.c_max_length // next_ncol]
                  )
                  / (2 * current_root)					)
           current_root *= root
        # Update
        __lowerCAmelCase							     =     new_inverse_c
        next_ncol *= 2
     # Unpack
     __lowerCAmelCase							     =     [round(x[0].real ,  8					) + round(x[0].imag ,  8					) * 1J for x in inverce_c]

     # Remove leading 0's
     while inverce_c[-1] == 0:
        inverce_c.pop()
     return inverce_c






  def __str__(    self			:		Dict					)							->						int:
     __lowerCAmelCase							     =     'A = ' + ' + '.join(
         f"""{coef}*x^{i}""" for coef, i in enumerate(self.polyA[: self.len_A]					)					)
     __lowerCAmelCase							     =     'B = ' + ' + '.join(
         f"""{coef}*x^{i}""" for coef, i in enumerate(self.polyB[: self.len_B]					)					)
     __lowerCAmelCase							     =     'A*B = ' + ' + '.join(
         f"""{coef}*x^{i}""" for coef, i in enumerate(self.product					)					)

     return f"""{a}\n{b}\n{c}"""


# Unit tests
if __name__ == "__main__":
     import doctest

     doctest.testmod()

