
import itertools


def 		_lowerCamelCase       (   _a = 1_0_0_0_0_0_0  ):
  """simple docstring"""




  _lowerCamelCase      =						[1]

  for i in itertools.count(len(_a  )  ):
    _lowerCamelCase      =						0
    for j in itertools.count(1  ):
      _lowerCamelCase      =						-1 if j % 2 == 0 else +1
      _lowerCamelCase      =						(j * j * 3 - j) // 2
      if index > i:
        break
      item += partitions[i - index] * sign
      item %= number
      index += j
      if index > i:
        break
      item += partitions[i - index] * sign
      item %= number

    if item == 0:
      return i
    partitions.append(_a  )

  return 0


if __name__ == "__main__":
  import doctest

  doctest.testmod()

  print(F'{solution() = }')






from __future__ import annotations

from collections.abc import Iterable
from dataclasses import dataclass
from typing import Any

class 		__magic_name__				:


  """simple docstring"""





  _UpperCamelCase						 = ("_front", "_back", "_len")

  @dataclass
  class 		__magic_name__				:


    """simple docstring"""





    _UpperCamelCase						 = None
    _UpperCamelCase						 = None
    _UpperCamelCase						 = None







  class 		__magic_name__				:


    """simple docstring"""





    _UpperCamelCase						 = ("_cur",)


    def __init__(					self	,		a__		):
      _lowerCamelCase      =						cur


    def __iter__(					self		):
      return self


    def     _UpperCAmelCase  (					self		):
      if self._cur is None:
        # finished iterating
        raise StopIteration
      _lowerCamelCase      =						self._cur.val
      _lowerCamelCase      =						self._cur.next_node

      return val







  def __init__(					self	,		a__ = None		):
    _lowerCamelCase      =						None
    _lowerCamelCase      =						None
    _lowerCamelCase      =						0

    if iterable is not None:
      # append every value to the deque
      for val in iterable:
        self.append(a__		)


  def     _UpperCAmelCase  (					self	,		a__		):
    _lowerCamelCase      =						self._Node(a__	,		a__	,		a__		)
    if self.is_empty():
      # front = back
      _lowerCamelCase      =						_lowerCamelCase      =						node
      _lowerCamelCase      =						1
    else:
      # connect nodes
      _lowerCamelCase      =						node
      _lowerCamelCase      =						self._back
      _lowerCamelCase      =						node  # assign new back to the new node

      self._len += 1

      # make sure there were no errors
      assert not self.is_empty(), "Error on appending value."


  def     _UpperCAmelCase  (					self	,		a__		):
    _lowerCamelCase      =						self._Node(a__	,		a__	,		a__		)
    if self.is_empty():
      # front = back
      _lowerCamelCase      =						_lowerCamelCase      =						node
      _lowerCamelCase      =						1
    else:
      # connect nodes
      _lowerCamelCase      =						self._front
      _lowerCamelCase      =						node
      _lowerCamelCase      =						node  # assign new front to the new node

      self._len += 1

      # make sure there were no errors
      assert not self.is_empty(), "Error on appending value."


  def     _UpperCAmelCase  (					self	,		a__		):
    for val in iterable:
      self.append(a__		)


  def     _UpperCAmelCase  (					self	,		a__		):
    for val in iterable:
      self.appendleft(a__		)


  def     _UpperCAmelCase  (					self		):
    assert not self.is_empty(), "Deque is empty."

    _lowerCamelCase      =						self._back
    _lowerCamelCase      =						self._back.prev_node  # set new back
    # drop the last node - python will deallocate memory automatically
    _lowerCamelCase      =						None

    self._len -= 1

    return topop.val


  def     _UpperCAmelCase  (					self		):
    assert not self.is_empty(), "Deque is empty."

    _lowerCamelCase      =						self._front
    _lowerCamelCase      =						self._front.next_node  # set new front and drop the first node
    _lowerCamelCase      =						None

    self._len -= 1

    return topop.val


  def     _UpperCAmelCase  (					self		):
    return self._front is None


  def __len__(					self		):
    return self._len


  def __eq__(					self	,		a__		):

    if not isinstance(a__	,		a__		):
      return NotImplemented

    _lowerCamelCase      =						self._front
    _lowerCamelCase      =						other._front

    # if the length of the dequeues are not the same, they are not equal
    if len(self		) != len(a__		):
      return False

    while me is not None and oth is not None:
      # compare every value
      if me.val != oth.val:
        return False
      _lowerCamelCase      =						me.next_node
      _lowerCamelCase      =						oth.next_node

    return True


  def __iter__(					self		):
    return Deque._Iterator(self._front		)


  def __repr__(					self		):
    _lowerCamelCase      =						[]
    _lowerCamelCase      =						self._front
    while aux is not None:
      # append the values in a list to display
      values_list.append(aux.val		)
      _lowerCamelCase      =						aux.next_node

    return f'''[{', '.join(repr(a__		) for val in values_list		)}]'''


if __name__ == "__main__":
  import doctest

  doctest.testmod()




