


import mpmath  # for roots of unity
import numpy as np



class        a					:





     def __init__(    self					:				List[Any]    ,	SCREAMING_SNAKE_CASE_					:				Union[str, Any]=None    ,	SCREAMING_SNAKE_CASE_					:				List[str]=None							):
        # Input as list
        __lowerCamelCase:				Tuple     =	list(poly_a or [0]							)[:]
        __lowerCamelCase:				Tuple     =	list(poly_b or [0]							)[:]

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

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

        # Add 0 to make lengths equal a power of 2
        __lowerCamelCase:				Tuple     =	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:				Union[str, Any]     =	complex(mpmath.root(x=1    ,	n=self.c_max_length    ,	k=1							)							)

        # The product
        __lowerCamelCase:				Tuple     =	self.__multiply()





     def  SCREAMING_SNAKE_CASE__       (    self					:				Tuple    ,	SCREAMING_SNAKE_CASE_					:				List[str]							):
        __lowerCamelCase:				Optional[int]     =	[[x] for x in self.polyA] if which == """A""" else [[x] for x in self.polyB]
        # Corner case
        if len(SCREAMING_SNAKE_CASE_							) <= 1:
           return dft[0]
        #
        __lowerCamelCase:				Any     =	self.c_max_length // 2
        while next_ncol > 0:
           __lowerCamelCase:				Union[str, Any]     =	[[] for i in range(SCREAMING_SNAKE_CASE_							)]
           __lowerCamelCase:				List[Any]     =	self.root**next_ncol

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





     def  SCREAMING_SNAKE_CASE__       (    self					:				Optional[Any]							):
        __lowerCamelCase:				List[str]     =	self.__dft("""A"""							)
        __lowerCamelCase:				Union[str, Any]     =	self.__dft("""B"""							)
        __lowerCamelCase:				Tuple     =	[[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:				Dict     =	2
        while next_ncol <= self.c_max_length:
           __lowerCamelCase:				List[Any]     =	[[] for i in range(SCREAMING_SNAKE_CASE_							)]
           __lowerCamelCase:				List[str]     =	self.root ** (next_ncol // 2)
           __lowerCamelCase:				Optional[int]     =	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:				Optional[Any]     =	new_inverse_c
           next_ncol *= 2
        # Unpack
        __lowerCamelCase:				Optional[Any]     =	[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					:				Optional[int]							):
        __lowerCamelCase:				Optional[Any]     =	"""A = """ + """ + """.join(
            F'{coef}*x^{i}' for coef, i in enumerate(self.polyA[: self.len_A]							)							)
        __lowerCamelCase:				Dict     =	"""B = """ + """ + """.join(
            F'{coef}*x^{i}' for coef, i in enumerate(self.polyB[: self.len_B]							)							)
        __lowerCamelCase:				str     =	"""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()






def     __lowerCAmelCase						(							)       ->							Optional[Any]:
   __lowerCamelCase:				List[str]     =	[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

   __lowerCamelCase:				List[str]     =	6
   __lowerCamelCase:				Optional[int]     =	1
   __lowerCamelCase:				int     =	1901

   __lowerCamelCase:				Tuple     =	0

   while year < 2001:
      day += 7

      if (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0):
         if day > days_per_month[month - 1] and month != 2:
            month += 1
            __lowerCamelCase:				Union[str, Any]     =	day - days_per_month[month - 2]
         elif day > 29 and month == 2:
            month += 1
            __lowerCamelCase:				List[Any]     =	day - 29
      else:
         if day > days_per_month[month - 1]:
            month += 1
            __lowerCamelCase:				Any     =	day - days_per_month[month - 2]

      if month > 12:
         year += 1
         __lowerCamelCase:				Dict     =	1

      if year < 2001 and day == 1:
         sundays += 1
   return sundays


if __name__ == "__main__":
   print(solution())


