"""
Problem 78: https://projecteuler.net/problem=78

Let p(n) represent the number of different ways in which n coins
can be separated into piles. For example, five coins can be separated
into piles in exactly seven different ways, so p(5)=7.

            OOOOO
            OOOO   O
            OOO   OO
            OOO   O   O
            OO   OO   O
            OO   O   O   O
            O   O   O   O   O
Find the least value of n for which p(n) is divisible by one million.
"""


# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/31
'''


'''
from p076 import charge
def solution(limit: int = 1000000) -> int:

    # similarly with Problem 76,77:

    money = 2
    while True:
        if charge(money, 1) % limit:
            money += 1
        else:
            return money

# RecursionError:
# maximum recursion depth exceeded in comparison
'''


CH = dict()  # {(money,minus):count}


def charge(money: int, minus: int):
    '''
    modification of p076.charge() without recursion

    >>> print(charge(5,1))
    7
    '''

    for m in range(money+1):
        for s in range(money, minus-1, -1):
            if (m, s) in CH:
                # print('repeat')
                continue
            if m == 0:
                CH[(m, s)] = 1
                continue
            k = m/s
            if k < 1:
                CH[(m, s)] = 0
                continue
            if 1 <= k < 2:
                CH[(m, s)] = 1
                continue
            if k == 2:
                CH[(m, s)] = 2
                continue
            k = int(k)
            CH[(m, s)] = sum(CH[(m-i*s, s+1)] for i in range(k+1))

    return CH[(money, minus)]


def solution1(limit: int = 1000000) -> int:

    money = 2
    while True:
        if charge(money, 1) % limit:
            print(money)
            money += 1
        else:
            return money

# also slow, can soulve ~10000
#####################################################################


PN = {0: 1}


def partitionfunction(n: int) -> int:
    '''
    ref: Wikipedia - Partition function (number theory)

    In number theory, the partition function p(n) represents
    the number of possible partitions of a non-negative integer n.
    For instance, p(4) = 5 because the integer 4 has the five partitions
    1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, and 4.

    The first few values of the partition function, starting with p(0) = 1, are:
    1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385,
    490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, ...

    >>> print(partitionfunction(100))
    190569292
    '''
    # if n in PN:
    #     return PN[n]

    pn = lambda n: PN[n] if n >= 0 else 0

    for i in range(1, n+1):
        klimit = int(((24*i+1)**0.5 + 1)/6)

        PN[i] = sum(int((-1)**(k+1))*pn(i-k*(3*k-1) // 2) for k in set(range(-1*klimit, klimit+1)) - {0})
        # print(i, PN[i])

    return PN[n]


def solution(limit: int = 1000000) -> int:

    partitionfunction(60000)

    n=2
    while True:
        if PN[n] % limit:
            # print(n)
            n += 1
        else:
            return n


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose = False)
    import time
    print(solution())
    # 55374