"""simple docstring"""






__lowerCAmelCase    :       str					     =[
    9_9_9,
    8_0_0,
    7_9_9,
    6_0_0,
    5_9_9,
    5_0_0,
    4_0_0,
    3_9_9,
    3_7_7,
    3_5_5,
    3_3_3,
    3_1_1,
    2_8_8,
    2_6_6,
    2_4_4,
    2_2_2,
    2_0_0,
    1_9_9,
    1_7_7,
    1_5_5,
    1_3_3,
    1_1_1,
    8_8,
    6_6,
    4_4,
    2_2,
    0,
]

__lowerCAmelCase    :       Dict					     =[
    9_9_9,
    9_7_6,
    9_5_2,
    9_2_8,
    9_0_5,
    8_8_2,
    8_5_8,
    8_5_7,
    8_1_0,
    7_6_2,
    7_1_5,
    7_1_4,
    5_7_2,
    4_2_9,
    4_2_8,
    2_8_6,
    2_8_5,
    2_3_8,
    1_9_0,
    1_4_3,
    1_4_2,
    1_1_8,
    9_5,
    7_1,
    4_7,
    2_4,
    0,
]

__lowerCAmelCase    :       Optional[int]					     =[
    9_9_9,
    9_8_8,
    9_7_7,
    9_6_6,
    9_5_5,
    9_4_4,
    9_3_3,
    9_2_2,
    9_1_1,
    9_0_0,
    8_9_9,
    8_7_9,
    8_5_9,
    8_4_0,
    8_2_0,
    8_0_0,
    7_9_9,
    7_6_6,
    7_3_3,
    7_0_0,
    6_9_9,
    6_5_0,
    6_0_0,
    5_9_9,
    5_0_0,
    4_9_9,
    4_0_0,
    3_9_9,
    3_5_0,
    3_0_0,
    2_9_9,
    2_6_6,
    2_3_3,
    2_0_0,
    1_9_9,
    1_7_9,
    1_5_9,
    1_4_0,
    1_2_0,
    1_0_0,
    9_9,
    8_8,
    7_7,
    6_6,
    5_5,
    4_4,
    3_3,
    2_2,
    1_1,
    0,
]

__lowerCAmelCase    :       Optional[int]					     =[
    9_9_9,
    9_9_5,
    9_9_2,
    9_8_9,
    9_8_5,
    9_8_1,
    9_7_8,
    9_7_5,
    9_7_1,
    9_6_7,
    9_6_4,
    9_6_1,
    9_5_7,
    9_5_6,
    9_5_1,
    9_4_7,
    9_4_2,
    9_3_7,
    9_3_3,
    9_2_8,
    9_2_3,
    9_1_9,
    9_1_4,
    9_1_3,
    9_0_8,
    9_0_3,
    8_9_7,
    8_9_2,
    8_8_7,
    8_8_1,
    8_7_6,
    8_7_1,
    8_7_0,
    8_6_4,
    8_5_8,
    8_5_2,
    8_4_6,
    8_4_0,
    8_3_4,
    8_2_8,
    8_2_7,
    8_2_0,
    8_1_3,
    8_0_6,
    7_9_9,
    7_9_2,
    7_8_5,
    7_8_4,
    7_7_7,
    7_7_0,
    7_6_3,
    7_5_6,
    7_4_9,
    7_4_2,
    7_4_1,
    7_3_3,
    7_2_4,
    7_1_6,
    7_0_7,
    6_9_9,
    6_9_8,
    6_8_8,
    6_7_7,
    6_6_6,
    6_5_6,
    6_5_5,
    6_4_5,
    6_3_4,
    6_2_3,
    6_1_3,
    6_1_2,
    5_9_8,
    5_8_4,
    5_7_0,
    5_6_9,
    5_5_5,
    5_4_1,
    5_2_7,
    5_2_6,
    5_0_5,
    4_8_4,
    4_8_3,
    4_6_2,
    4_4_0,
    4_3_9,
    3_9_6,
    3_9_5,
    3_5_2,
    3_5_1,
    3_0_8,
    3_0_7,
    2_6_4,
    2_6_3,
    2_2_0,
    2_1_9,
    1_7_6,
    1_3_2,
    8_8,
    4_4,
    0,
]

__lowerCAmelCase    :       List[Any]					     =[
    9_9_9,
    9_9_7,
    9_9_5,
    9_9_2,
    9_9_0,
    9_8_8,
    9_8_6,
    9_8_4,
    9_8_1,
    9_7_9,
    9_7_7,
    9_7_5,
    9_7_2,
    9_7_0,
    9_6_8,
    9_6_6,
    9_6_4,
    9_6_1,
    9_5_9,
    9_5_7,
    9_5_6,
    9_5_4,
    9_5_1,
    9_4_9,
    9_4_6,
    9_4_4,
    9_4_1,
    9_3_9,
    9_3_6,
    9_3_4,
    9_3_1,
    9_2_9,
    9_2_6,
    9_2_4,
    9_2_1,
    9_1_9,
    9_1_6,
    9_1_4,
    9_1_3,
    9_1_0,
    9_0_7,
    9_0_5,
    9_0_2,
    8_9_9,
    8_9_6,
    8_9_3,
    8_9_1,
    8_8_8,
    8_8_5,
    8_8_2,
    8_7_9,
    8_7_7,
    8_7_4,
    8_7_1,
    8_7_0,
    8_6_7,
    8_6_4,
    8_6_1,
    8_5_8,
    8_5_5,
    8_5_2,
    8_4_9,
    8_4_6,
    8_4_3,
    8_4_0,
    8_3_7,
    8_3_4,
    8_3_1,
    8_2_8,
    8_2_7,
    8_2_4,
    8_2_1,
    8_1_7,
    8_1_4,
    8_1_1,
    8_0_8,
    8_0_4,
    8_0_1,
    7_9_8,
    7_9_5,
    7_9_1,
    7_8_8,
    7_8_5,
    7_8_4,
    7_8_0,
    7_7_7,
    7_7_4,
    7_7_0,
    7_6_6,
    7_6_3,
    7_6_0,
    7_5_6,
    7_5_2,
    7_4_9,
    7_4_6,
    7_4_2,
    7_4_1,
    7_3_7,
    7_3_3,
    7_3_0,
    7_2_6,
    7_2_2,
    7_1_8,
    7_1_4,
    7_1_0,
    7_0_7,
    7_0_3,
    6_9_9,
    6_9_8,
    6_9_4,
    6_9_0,
    6_8_5,
    6_8_1,
    6_7_7,
    6_7_3,
    6_6_9,
    6_6_4,
    6_6_0,
    6_5_6,
    6_5_5,
    6_5_0,
    6_4_6,
    6_4_1,
    6_3_6,
    6_3_2,
    6_2_7,
    6_2_2,
    6_1_8,
    6_1_3,
    6_1_2,
    6_0_7,
    6_0_2,
    5_9_6,
    5_9_1,
    5_8_6,
    5_8_0,
    5_7_5,
    5_7_0,
    5_6_9,
    5_6_3,
    5_5_7,
    5_5_1,
    5_4_5,
    5_3_9,
    5_3_3,
    5_2_7,
    5_2_6,
    5_1_9,
    5_1_2,
    5_0_5,
    4_9_8,
    4_9_1,
    4_8_4,
    4_8_3,
    4_7_4,
    4_6_6,
    4_5_7,
    4_4_9,
    4_4_0,
    4_3_9,
    4_2_8,
    4_1_8,
    4_0_7,
    3_9_6,
    3_9_5,
    3_8_1,
    3_6_6,
    3_5_2,
    3_5_1,
    3_3_0,
    3_0_8,
    3_0_7,
    2_8_6,
    2_6_4,
    2_6_3,
    2_4_2,
    2_2_0,
    2_1_9,
    1_7_6,
    1_7_5,
    1_3_2,
    1_3_1,
    8_8,
    4_4,
    0,
]

__lowerCAmelCase    :       str					     =[
    9_9_9,
    9_9_1,
    9_8_2,
    9_7_4,
    9_6_6,
    9_5_8,
    9_5_0,
    9_4_1,
    9_3_3,
    9_2_5,
    9_1_6,
    9_0_8,
    9_0_0,
    8_9_9,
    8_7_4,
    8_5_0,
    8_2_5,
    8_0_0,
    7_9_9,
    7_0_0,
    6_0_0,
    5_0_0,
    4_0_0,
    3_0_0,
    2_0_0,
    1_0_0,
    0,
]

__lowerCAmelCase    :       Dict					     =[
    9_9_9,
    9_9_2,
    9_8_5,
    9_7_8,
    9_7_1,
    9_6_4,
    9_5_7,
    9_4_9,
    9_4_2,
    9_3_5,
    9_2_8,
    9_2_1,
    9_1_4,
    9_0_7,
    9_0_0,
    8_9_9,
    8_7_9,
    8_5_9,
    8_4_0,
    8_2_0,
    8_0_0,
    7_9_9,
    7_6_6,
    7_3_3,
    7_0_0,
    6_9_9,
    6_5_0,
    6_0_0,
    5_9_9,
    5_0_0,
    4_9_9,
    4_0_0,
    3_9_9,
    3_0_0,
    2_9_9,
    2_0_0,
    1_9_9,
    1_0_0,
    9_9,
    0,
]

__lowerCAmelCase    :       Optional[Any]					     =[
    9_9_9,
    9_9_6,
    9_9_2,
    9_8_9,
    9_8_5,
    9_8_2,
    9_7_9,
    9_7_5,
    9_7_2,
    9_6_8,
    9_6_5,
    9_6_1,
    9_5_8,
    9_5_5,
    9_5_1,
    9_4_8,
    9_4_4,
    9_4_1,
    9_3_8,
    9_3_4,
    9_3_1,
    9_2_7,
    9_2_4,
    9_2_0,
    9_1_7,
    9_1_4,
    9_1_0,
    9_0_7,
    9_0_3,
    9_0_0,
    8_9_9,
    8_9_1,
    8_8_4,
    8_7_6,
    8_6_9,
    8_6_1,
    8_5_3,
    8_4_6,
    8_3_8,
    8_3_0,
    8_2_3,
    8_1_5,
    8_0_8,
    8_0_0,
    7_9_9,
    7_8_8,
    7_7_7,
    7_6_6,
    7_5_5,
    7_4_4,
    7_3_3,
    7_2_2,
    7_1_1,
    7_0_0,
    6_9_9,
    6_8_8,
    6_7_7,
    6_6_6,
    6_5_5,
    6_4_4,
    6_3_3,
    6_2_2,
    6_1_1,
    6_0_0,
    5_9_9,
    5_8_5,
    5_7_1,
    5_5_7,
    5_4_2,
    5_2_8,
    5_1_4,
    5_0_0,
    4_9_9,
    4_8_5,
    4_7_1,
    4_5_7,
    4_4_2,
    4_2_8,
    4_1_4,
    4_0_0,
    3_9_9,
    3_7_9,
    3_5_9,
    3_4_0,
    3_2_0,
    3_0_0,
    2_9_9,
    2_7_9,
    2_5_9,
    2_4_0,
    2_2_0,
    2_0_0,
    1_9_9,
    1_6_6,
    1_3_3,
    1_0_0,
    9_9,
    6_6,
    3_3,
    0,
]




"""simple docstring"""






from __future__ import annotations

from collections.abc import Callable

__lowerCAmelCase    :       str					     =list[list[float | int]]


def 			UpperCAmelCase__       (				lowerCAmelCase__     :Matrix					,		lowerCAmelCase__     :Matrix		) ->    Matrix:
      '''simple docstring'''


      lowercase														=	len(lowerCAmelCase__		)
      lowercase														=	[[0 for _ in range(size + 1		)] for _ in range(lowerCAmelCase__		)]
      lowercase														=	42
      lowercase														=	42
      lowercase														=	42
      lowercase														=	42
      lowercase														=	42
      lowercase														=	42

      for row in range(lowerCAmelCase__		):
            for col in range(lowerCAmelCase__		):
                  lowercase														=	matrix[row][col]

            lowercase														=	vector[row][0]

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

            for rowa in range(row + 1					,		lowerCAmelCase__		):
                  lowercase														=	augmented[rowa][col] / augmented[row][col]
                  lowercase														=	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__		):
                  lowercase														=	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]					,		1_0		)] for row in range(lowerCAmelCase__		)
      ]


def 			UpperCAmelCase__       (				lowerCAmelCase__     :list[int]		) ->    Callable[[int], int]:
      '''simple docstring'''


      lowercase														=	len(lowerCAmelCase__		)
      lowercase														=	[[0 for _ in range(lowerCAmelCase__		)] for _ in range(lowerCAmelCase__		)]
      lowercase														=	[[0] for _ in range(lowerCAmelCase__		)]
      lowercase														=	42
      lowercase														=	42
      lowercase														=	42
      lowercase														=	42

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

      lowercase														=	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 			UpperCAmelCase__       (				lowerCAmelCase__     :int		) ->    int:
      '''simple docstring'''


      return (
          1
          - variable
          + variable**2
          - variable**3
          + variable**4
          - variable**5
          + variable**6
          - variable**7
          + variable**8
          - variable**9
          + variable**1_0
      )


def 			UpperCAmelCase__       (				lowerCAmelCase__     :Callable[[int], int] = question_function					,		lowerCAmelCase__     :int = 1_0		) ->    int:
      '''simple docstring'''


      lowercase														=	[func(lowerCAmelCase__		) for x_val in range(1					,		order + 1		)]

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

      lowercase														=	0
      lowercase														=	42
      lowercase														=	42

      for poly in polynomials:
            lowercase														=	1
            while func(lowerCAmelCase__		) == poly(lowerCAmelCase__		):
                  x_val += 1

            ret += poly(lowerCAmelCase__		)

      return ret


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



