#include <cassert>
#include <iostream>

// Integer partitions
//
// The number of ways that a non-negative integer n
// can be written as a sum of positive integers,
// ignoring order, is called the number of integer
// partitions of n. It is represented by p(n).
//
// For example:
//
//     5 = 5
//       = 4 + 1
//       = 3 + 2
//       = 3 + 1 + 1
//       = 2 + 2 + 1
//       = 2 + 1 + 1 + 1
//       = 1 + 1 + 1 + 1 + 1.
//
// Therefore:
//
//     p(5) = 7.
//
// By convention:
//
//     p(0) = 1.
//
// There is one way to partition zero: use no
// positive integers at all.
//
//
//
// A generating function
//
// You read that p(n) is the coefficient of x^n in:
//
//             infinity
//              -----
//               | |       1
//               | |   ---------.
//               | |   1 - x^k
//              -----
//               k = 1
//
// That is:
//
//       1        1        1
//   ------- * ------- * ------- * ...
//   1 - x     1 - x^2  1 - x^3
//
//
// Expanding this product begins:
//
//                        2      3      4      5
//     1 + x + 2x + 3x + 5x + 7x
//
//            6       7       8       9        10
//        + 11x  + 15x  + 22x  + 30x  + 42x
//
//        + ...
//
//
// Note:
//
//     (1 + x)(1 + x^2)(1 + x^3)...
//
// is a different generating function. It counts
// partitions into DISTINCT parts, because each
// power x^k can be selected at most once.
//
//
//
// You would rather calculate p(n) directly.
//
// Looking in Abramowitz and Stegun, you find:
//
//                 n
//               -----
//            1   \
//     p(n) = -    )   sigma_1(k) p(n - k),
//            n   /
//               -----
//                k = 1
//
// where:
//
//     sigma_1(k)
//
// is the sum of the positive divisors of k.
//
// For example:
//
//     sigma_1(6)
//
//       = 1 + 2 + 3 + 6
//
//       = 12.
//
// If p is prime:
//
//     sigma_1(p) = 1 + p.
//
//
//
// You also find Euler's recurrence involving the
// generalized pentagonal numbers:
//
//     1, 2, 5, 7, 12, 15, 22, 26, ...
//
// These numbers have the form:
//
//     k(3k - 1)        k(3k + 1)
//     ---------   and  ---------
//         2                2
//
// for:
//
//     k = 1, 2, 3, ...
//
// Euler's recurrence is:
//
//     p(n)
//
//       = p(n - 1) + p(n - 2)
//
//         - p(n - 5) - p(n - 7)
//
//         + p(n - 12) + p(n - 15)
//
//         - p(n - 22) - p(n - 26)
//
//         + ...
//
// where we stop whenever the argument of p would
// become negative.
//
// Notice the signs:
//
//     + + - - + + - - ...
//
//
// QUESTION:
//
//     Which recursive implementation is faster?
//
// Be careful: both implementations below are
// deliberately recursive and do NOT use
// memoization.
//
// They therefore repeatedly calculate many of the
// same values.

// Function declarations
int main();

unsigned long long integer_partitions_sigma_rec(
    unsigned int const n
);

unsigned long long integer_partitions_rec(
    unsigned int const n
);

unsigned long long sigma(
    unsigned int const n,
    unsigned int const k = 1
);

unsigned long long pow(
    unsigned long long n,
    unsigned int m
);


// Function definitions
int main() {
    // These should be:
    //
    //     p(1)  =    1
    //     p(2)  =    2
    //     p(3)  =    3
    //     p(4)  =    5
    //     p(5)  =    7
    //     p(6)  =   11
    //     p(7)  =   15
    //     p(8)  =   22
    //     p(9)  =   30
    //     p(10) =   42
    //     p(11) =   56
    //     p(12) =   77
    //     p(13) =  101
    //     p(14) =  135
    //     p(15) =  176
    //     p(16) =  231
    //     p(17) =  297
    //     p(18) =  385
    //     p(19) =  490
    //     p(20) =  627
    //     p(21) =  792
    //     p(22) = 1002
    //     p(23) = 1255
    //     p(24) = 1575
    //     p(25) = 1958
    //     p(26) = 2436
    //     p(27) = 3010
    //     p(28) = 3718
    //
    // First use the recurrence involving sigma_1(k).

    for ( unsigned int n{ 1 }; n <= 28; ++n ) {
        std::cout << "p(" << n << ") = "
                  << integer_partitions_sigma_rec( n )
                  << std::endl;
    }

    std::cout << std::endl;


    // Now use Euler's generalized pentagonal-number
    // recurrence.

    for ( unsigned int n{ 1 }; n <= 28; ++n ) {
        std::cout << "p(" << n << ") = "
                  << integer_partitions_rec( n )
                  << std::endl;
    }

    return 0;
}


// Calculate:
//
//     sigma_k(n)
//
// which is the sum of the kth powers of the
// positive divisors of n.
//
// For example:
//
//     sigma_1(6)
//       = 1 + 2 + 3 + 6
//       = 12.
//
// and:
//
//     sigma_2(6)
//       = 1^2 + 2^2 + 3^2 + 6^2
//       = 50.

unsigned long long sigma(
    unsigned int const n,
    unsigned int const k
) {
    assert( n >= 1 );

    unsigned long long sum{ 0 };

    for ( unsigned int d{ 1 }; d <= n; ++d ) {
        if ( n%d == 0 ) {
            sum += pow( d, k );
        }
    }

    return sum;
}


// Calculate:
//
//     n^m
//
// using exponentiation by squaring.
//
// For example, suppose:
//
//     m = 42.
//
// In binary:
//
//     42 = 101010.
//
// Thus:
//
//     42 = 32 + 8 + 2,
//
// and therefore:
//
//     n^42 = n^32 * n^8 * n^2.
//
// We repeatedly square n:
//
//     n, n^2, n^4, n^8, n^16, n^32, ...
//
// and multiply the appropriate powers into the
// result.
//
// This requires Theta(log(m)) multiplications
// rather than Theta(m) multiplications.

unsigned long long pow(
    unsigned long long n,
    unsigned int m
) {
    unsigned long long result{ 1 };

    while ( m > 0 ) {
        if ( (m & 1) == 1 ) {
            result *= n;
        }

        n *= n;
        m >>= 1;
    }

    return result;
}


// Your implementations here

unsigned long long integer_partitions_sigma_rec(
    unsigned int const n
) {
    return 0;
}


unsigned long long integer_partitions_rec(
    unsigned int const n
) {
    return 0;
}














































// Hint 1
//
// By definition:
//
//     p(0) = 1.
//
// This is important.
//
// For example, Euler's recurrence gives:
//
//     p(5)
//
//       = p(4) + p(3) - p(0).
//
// Thus:
//
//     p(5)
//
//       = 5 + 3 - 1
//
//       = 7.
//
//
//
// For the sigma recurrence:
//
//                 n
//               -----
//            1   \
//     p(n) = -    )   sigma_1(k) p(n - k),
//            n   /
//               -----
//                k = 1
//
// simply translate the summation into a loop over:
//
//     k = 1, 2, ..., n.














































// Hint 2
//
// For Euler's recurrence, calculate the two
// generalized pentagonal numbers:
//
//     k(3k - 1)
//     ---------
//         2
//
// and:
//
//     k(3k + 1)
//     ---------
//         2.
//
// For:
//
//     k = 1,
//
// these are:
//
//     1 and 2.
//
// For:
//
//     k = 2,
//
// these are:
//
//     5 and 7.
//
// For:
//
//     k = 3,
//
// these are:
//
//     12 and 15.
//
// For:
//
//     k = 4,
//
// these are:
//
//     22 and 26.
//
// Thus:
//
//     p(n)
//
//       = p(n - 1) + p(n - 2)
//
//         - p(n - 5) - p(n - 7)
//
//         + p(n - 12) + p(n - 15)
//
//         - p(n - 22) - p(n - 26)
//
//         + ...
//
//
// Stop using a generalized pentagonal number as
// soon as it exceeds n.
//
//
//
// The signs come in pairs:
//
//     + +
//
//     - -
//
//     + +
//
//     - -
//
//     ...
//
// Thus, when:
//
//     k = 1, 3, 5, ...
//
// add the terms.
//
// When:
//
//     k = 2, 4, 6, ...
//
// subtract the terms.














































// Here is one solution:

/*
unsigned long long integer_partitions_sigma_rec(
    unsigned int const n
) {
    if ( n == 0 ) {
        return 1;
    }

    unsigned long long sum{ 0 };

    for ( unsigned int k{ 1 }; k <= n; ++k ) {
        sum += sigma( k )
             * integer_partitions_sigma_rec( n - k );
    }

    assert( sum%n == 0 );

    return sum/n;
}


unsigned long long integer_partitions_rec(
    unsigned int const n
) {
    if ( n == 0 ) {
        return 1;
    }

    long long sum{ 0 };

    for ( unsigned int k{ 1 }; ; ++k ) {
        unsigned int const pentagonal_minus{
            k*(3*k - 1)/2
        };

        if ( pentagonal_minus > n ) {
            break;
        }

        unsigned int const pentagonal_plus{
            k*(3*k + 1)/2
        };

        long long const sign{
            (k%2 == 1) ? 1 : -1
        };

        sum += sign
             * static_cast<long long>(
                   integer_partitions_rec(
                       n - pentagonal_minus
                   )
               );

        if ( pentagonal_plus <= n ) {
            sum += sign
                 * static_cast<long long>(
                       integer_partitions_rec(
                           n - pentagonal_plus
                       )
                   );
        }
    }

    assert( sum >= 0 );

    return static_cast<unsigned long long>( sum );
}
*/












































// Understanding the sigma recurrence
//
// Consider:
//
//                 n
//               -----
//            1   \
//     p(n) = -    )   sigma_1(k) p(n - k).
//            n   /
//               -----
//                k = 1
//
// For n = 5:
//
//     5*p(5)
//
//       = sigma_1(1)*p(4)
//
//         + sigma_1(2)*p(3)
//
//         + sigma_1(3)*p(2)
//
//         + sigma_1(4)*p(1)
//
//         + sigma_1(5)*p(0).
//
//
// The divisor sums are:
//
//     sigma_1(1) = 1
//
//     sigma_1(2) = 1 + 2
//                = 3
//
//     sigma_1(3) = 1 + 3
//                = 4
//
//     sigma_1(4) = 1 + 2 + 4
//                = 7
//
//     sigma_1(5) = 1 + 5
//                = 6.
//
// Therefore:
//
//     5*p(5)
//
//       = 1*p(4)
//         + 3*p(3)
//         + 4*p(2)
//         + 7*p(1)
//         + 6*p(0)
//
//       = 1*5 + 3*3 + 4*2 + 7*1 + 6*1
//
//       = 35.
//
// Thus:
//
//     p(5) = 7.
//
//
//
// Understanding Euler's recurrence
//
// The generalized pentagonal numbers are:
//
//     1, 2, 5, 7, 12, 15, 22, 26, ...
//
// For n = 5, only:
//
//     1, 2, 5
//
// are relevant.
//
// The corresponding signs are:
//
//     +, +, -.
//
// Therefore:
//
//     p(5)
//
//       = p(4) + p(3) - p(0)
//
//       = 5 + 3 - 1
//
//       = 7.
//
//
//
// Which implementation is faster?
//
// Look at how many recursive calls each formula
// requests.
//
// The sigma recurrence for p(n) uses:
//
//     p(n - 1)
//     p(n - 2)
//     p(n - 3)
//     ...
//     p(0).
//
// Thus, one call to p(n) recursively requests ALL
// smaller partition values.
//
//
//
// Euler's recurrence requests only:
//
//     p(n - 1)
//     p(n - 2)
//     p(n - 5)
//     p(n - 7)
//     p(n - 12)
//     p(n - 15)
//     ...
//
// The indices being subtracted are the generalized
// pentagonal numbers.
//
// There are far fewer of these.
//
// Consequently, among THESE TWO naive recursive
// implementations, Euler's recurrence requires far
// fewer recursive calls and is dramatically faster
// as n increases.
//
//
//
// However, there is a much more important issue.
//
// BOTH implementations repeatedly calculate the
// same values.
//
// For example, while calculating p(20), we may
// calculate:
//
//     p(10)
//
// many different times.
//
// Each of those calculations then recursively
// calculates smaller values again.
//
// This is repeated work.
//
//
//
// Memoization
//
// Suppose the first time we calculate:
//
//     p(10) = 42,
//
// we store that result.
//
// The next time we need p(10), we simply look up:
//
//     42
//
// rather than recalculating it.
//
// This technique is called:
//
//     memoization.
//
// It can transform a recursive algorithm that
// repeatedly solves the same subproblems into a
// dramatically more efficient algorithm.
//
// We will encounter this idea again when studying
// dynamic programming.
//
//
//
// There are therefore really two questions:
//
//     1. Which RECURRENCE requires fewer terms?
//
//     2. Which IMPLEMENTATION avoids repeated work?
//
// Euler's generalized pentagonal-number recurrence
// is particularly attractive because only about
// sqrt(n) generalized pentagonal numbers are at
// most n.
//
// With memoization, or by calculating:
//
//     p(0), p(1), p(2), ..., p(n)
//
// in order and storing the results, the calculation
// becomes vastly more practical.
//
//
//
// Why are there only about sqrt(n) terms?
//
// The generalized pentagonal numbers have the
// form:
//
//     k(3k +/- 1)
//     -----------.
//          2
//
// For large k, this is approximately:
//
//     3*k^2
//     -----.
//       2
//
// To remain no larger than n, we therefore need
// approximately:
//
//     k^2 <= 2*n/3.
//
// Thus:
//
//     k
//
// is proportional to:
//
//     sqrt(n).
//
// This is why each value p(n) requires only on the
// order of sqrt(n) earlier partition values when
// Euler's recurrence is used.
//
//
//
// A note about signed and unsigned integers
//
// The partition numbers themselves are positive,
// so it is natural to return:
//
//     unsigned long long.
//
// However, Euler's recurrence contains subtraction:
//
//     + + - - + + - - ...
//
// Consequently, the running sum should be signed:
//
//     long long sum{ 0 };
//
// We return an unsigned value only after the entire
// sum has been calculated.
//
// This is also why an expression such as:
//
//     pow( -1, k - 1 )
//
// should NOT be used with our unsigned pow()
// function.
//
// The value:
//
//     -1
//
// cannot be represented as an unsigned integer in
// the usual mathematical sense.
//
// More importantly, the intent is much clearer if
// we write:
//
//     (k%2 == 1) ? 1 : -1.
//
//
//
// Integer overflow
//
// There is another limitation.
//
// Partition numbers grow quickly.
//
// For example:
//
//     p(100) = 79270...
//
// is already much larger than the values shown in
// our first table, and eventually even an
// unsigned long long is insufficient.
//
// Thus, changing from:
//
//     unsigned long
//
// to:
//
//     unsigned long long
//
// delays overflow but does not eliminate it.
//
// Fixed-width integer types always have a limit.
//
//
//
// Questions:
//
// 1. Why is:
//
//        p(0) = 1?
//
// 2. How many partitions does 5 have?
//
// 3. Why does:
//
//        (1 + x)(1 + x^2)(1 + x^3)...
//
//    count partitions into distinct parts rather
//    than ordinary integer partitions?
//
// 4. What generating function produces p(n)?
//
// 5. What is sigma_1(6)?
//
// 6. Use the sigma recurrence to calculate p(5).
//
// 7. What are the first eight generalized
//    pentagonal numbers?
//
// 8. Why do the signs in Euler's recurrence occur
//    in pairs:
//
//        + + - - + + - - ... ?
//
// 9. Use Euler's recurrence to calculate p(5).
//
// 10. Why is the naive implementation using Euler's
//     recurrence faster than the naive implementation
//     using the sigma recurrence?
//
// 11. What repeated calculations occur in BOTH
//     recursive implementations?
//
// 12. How could memoization eliminate these repeated
//     calculations?
//
// 13. Why are there only approximately sqrt(n)
//     generalized pentagonal numbers less than n?
//
// 14. Why must the running sum in Euler's recurrence
//     be signed even though p(n) itself is positive?
//
//
//
// The most important algorithmic lesson is not the
// rather remarkable mathematics of partitions.
//
// It is that a recurrence relation and an efficient
// algorithm are NOT the same thing.
//
// A recurrence may give us a perfectly correct way
// to calculate a value recursively, while a direct
// implementation may repeat enormous amounts of
// work.
//
// Recognizing repeated subproblems:
//
//     calculate something once,
//     remember the result,
//     reuse it later
//
// leads naturally to:
//
//     memoization
//
// and, more generally:
//
//     dynamic programming.