#include <cassert>
#include <iostream>

// Partitions into distinct parts
//
// The number of ways that a non-negative integer n
// can be written as a sum of DISTINCT positive
// integers, ignoring order, is represented by q(n).
//
// For example:
//
//     5 = 5
//       = 4 + 1
//       = 3 + 2
//
// so:
//
//     q(5) = 3.
//
// Similarly:
//
//     6 = 6
//       = 5 + 1
//       = 4 + 2
//       = 3 + 2 + 1
//
// so:
//
//     q(6) = 4.
//
// Finally:
//
//     7 = 7
//       = 6 + 1
//       = 5 + 2
//       = 4 + 3
//       = 4 + 2 + 1
//
// so:
//
//     q(7) = 5.
//
// By convention:
//
//     q(0) = 1.
//
// There is one way to partition zero: use no
// positive integers at all.
//
//
//
// A generating function
//
// You read that q(n) is the coefficient of x^n in:
//
//     (1 + x)(1 + x^2)(1 + x^3)(1 + x^4)...
//
// Expanding this product begins:
//
//                       2      3      4      5
//     1 + x + x + 2x + 2x + 3x
//
//           6      7      8      9       10
//       + 4x + 5x + 6x + 8x + 10x
//
//       + ...
//
//
// Why does this product count partitions into
// distinct parts?
//
// From each factor:
//
//     (1 + x^k)
//
// we have exactly two choices:
//
//     choose 1
//
// or:
//
//     choose x^k.
//
// Thus, the integer k can occur either:
//
//     zero times
//
// or:
//
//     one time.
//
// It cannot occur twice.
//
// Consequently, the product counts partitions in
// which all parts are distinct.
//
//
//
// You would rather calculate q(n) directly.
//
// Looking in Abramowitz and Stegun, you find the
// recurrence:
//
//               n
//             -----
//          1  \
//   q(n) = -   )   q(n - k)
//          n  /
//             -----
//              k = 1
//
//              * [sigma_1(k) - 2*sigma_1(k/2)].
//
// Here:
//
//     sigma_1(k)
//
// is the sum of the positive divisors of k.
//
// For example:
//
//     sigma_1(6)
//
//       = 1 + 2 + 3 + 6
//
//       = 12.
//
// For a prime number p:
//
//     sigma_1(p) = 1 + p.
//
//
//
// There is one detail requiring interpretation.
//
// If k is odd, then:
//
//     k/2
//
// is not an integer.
//
// In the mathematical formula, we interpret:
//
//     sigma_1(k/2) = 0
//
// whenever k/2 is not an integer.
//
// Therefore:
//
//     if k is odd:
//
//         sigma_1(k) - 2*sigma_1(k/2)
//
//       = sigma_1(k).
//
//
//     if k is even:
//
//         sigma_1(k) - 2*sigma_1(k/2)
//
// is calculated normally.
//
//
//
// Implement this recurrence.
//
// QUESTION:
//
//     How does this recursive implementation behave
//     as n increases?
//
//     Do you recognize the same problem we saw with
//     our recursive implementations of p(n)?

// Function declarations
int main();

unsigned long long distinct_integer_partitions(
    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:
    //
    //     q(0)  =   1
    //     q(1)  =   1
    //     q(2)  =   1
    //     q(3)  =   2
    //     q(4)  =   2
    //     q(5)  =   3
    //     q(6)  =   4
    //     q(7)  =   5
    //     q(8)  =   6
    //     q(9)  =   8
    //     q(10) =  10
    //     q(11) =  12
    //     q(12) =  15
    //     q(13) =  18
    //     q(14) =  22
    //     q(15) =  27
    //     q(16) =  32
    //     q(17) =  38
    //     q(18) =  46
    //     q(19) =  54
    //     q(20) =  64
    //     q(21) =  76
    //     q(22) =  89
    //     q(23) = 104
    //     q(24) = 122
    //     q(25) = 142
    //     q(26) = 165
    //     q(27) = 192
    //     q(28) = 222
    //     q(29) = 256

    for ( unsigned int n{ 0 }; n <= 29; ++n ) {
        std::cout << "q(" << n << ") = "
                  << distinct_integer_partitions( 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 implementation here

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














































// Hint 1
//
// By definition:
//
//     q(0) = 1.
//
// This is important because the recurrence may
// eventually request:
//
//     q(n - k)
//
// where:
//
//     k = n.
//
// In that case:
//
//     q(n - k) = q(0).
//
//
//
// Translate:
//
//               n
//             -----
//          1  \
//   q(n) = -   )   q(n - k)
//          n  /
//             -----
//              k = 1
//
//              * [sigma_1(k) - 2*sigma_1(k/2)]
//
// directly into a loop:
//
//     k = 1, 2, ..., n.
//
// For each k, recursively calculate:
//
//     q(n - k).














































// Hint 2
//
// The expression:
//
//     sigma_1(k/2)
//
// requires some care.
//
// Mathematically, sigma_1 is defined here only for
// positive integers.
//
// If k is odd:
//
//     k/2
//
// is not an integer, so the term:
//
//     sigma_1(k/2)
//
// is interpreted as zero.
//
// Thus:
//
//     k odd:
//
//         sigma_1(k) - 2*sigma_1(k/2)
//
//       = sigma_1(k).
//
//
// If k is even:
//
//         sigma_1(k) - 2*sigma_1(k/2)
//
// is calculated normally.
//
//
//
// Be careful:
//
// C++ integer division does NOT automatically give
// the mathematical interpretation we want.
//
// For example:
//
//     5/2
//
// in C++ is:
//
//     2.
//
// But the mathematical formula does NOT mean:
//
//     sigma_1(5/2) = sigma_1(2).
//
// Instead, because 5/2 is not an integer:
//
//     sigma_1(5/2) = 0.
//
// Therefore, test whether k is even BEFORE calling:
//
//     sigma( k/2 ).














































// Here is one solution:

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

    unsigned long long sum{ 0 };

    for ( unsigned int k{ 1 }; k <= n; ++k ) {
        unsigned long long coefficient{
            sigma( k )
        };

        if ( k%2 == 0 ) {
            coefficient -= 2*sigma( k/2 );
        }

        sum += coefficient
             * distinct_integer_partitions( n - k );
    }

    assert( sum%n == 0 );

    return sum/n;
}
*/












































// Understanding the recurrence
//
// Let us calculate q(5).
//
// The recurrence says:
//
//     5*q(5)
//
//       = q(4)[sigma_1(1)]
//
//         + q(3)[sigma_1(2) - 2*sigma_1(1)]
//
//         + q(2)[sigma_1(3)]
//
//         + q(1)[sigma_1(4) - 2*sigma_1(2)]
//
//         + q(0)[sigma_1(5)].
//
//
//
// We know:
//
//     q(0) = 1
//     q(1) = 1
//     q(2) = 1
//     q(3) = 2
//     q(4) = 2.
//
// Also:
//
//     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*q(5)
//
//       = 2*(1)
//
//         + 2*(3 - 2*1)
//
//         + 1*(4)
//
//         + 1*(7 - 2*3)
//
//         + 1*(6)
//
//       = 2 + 2 + 4 + 1 + 6
//
//       = 15.
//
// Thus:
//
//     q(5) = 3.
//
// This agrees with our direct enumeration:
//
//     5
//     4 + 1
//     3 + 2.
//
//
//
// Why is q(0) equal to 1?
//
// At first:
//
//     q(0) = 1
//
// may seem peculiar.
//
// After all, how can we partition zero?
//
// The answer is that there is exactly one empty
// partition:
//
//     use no parts.
//
// This convention is not arbitrary.
//
// It allows the recurrence and the generating
// function to work naturally.
//
// In the generating function:
//
//     (1 + x)(1 + x^2)(1 + x^3)...
//
// choosing:
//
//     1
//
// from every factor produces:
//
//     1 = x^0.
//
// Thus, the coefficient of x^0 is 1.
//
// Therefore:
//
//     q(0) = 1.
//
//
//
// Why does the generating function work?
//
// Consider:
//
//     (1 + x)(1 + x^2)(1 + x^3)...
//
// Suppose we want the coefficient of:
//
//     x^5.
//
// From each factor:
//
//     (1 + x^k)
//
// we either:
//
//     do not use k,
//
// or:
//
//     use k exactly once.
//
//
//
// For example, choosing:
//
//     x^5
//
// from:
//
//     (1 + x^5)
//
// gives the partition:
//
//     5.
//
//
//
// Choosing:
//
//     x
//
// and:
//
//     x^4
//
// gives:
//
//     x*x^4 = x^5,
//
// corresponding to:
//
//     4 + 1.
//
//
//
// Choosing:
//
//     x^2
//
// and:
//
//     x^3
//
// gives:
//
//     x^2*x^3 = x^5,
//
// corresponding to:
//
//     3 + 2.
//
//
//
// These are exactly the three partitions of 5
// into distinct parts.
//
// Thus, the coefficient of x^5 is:
//
//     3.
//
//
//
// Compare ordinary and distinct partitions
//
// Previously, we considered:
//
//     p(n),
//
// the number of unrestricted integer partitions.
//
// Its generating function is:
//
//       1        1        1
//   ------- * ------- * ------- * ...
//   1 - x     1 - x^2  1 - x^3
//
//
// Why?
//
// Recall:
//
//        1
//     -------
//
//     1 - x^k
//
// expands as:
//
//                 2k    3k
//     1 + x^k + x   + x   + ...
//
// Thus, the part k may appear:
//
//     zero times,
//     once,
//     twice,
//     three times,
//     ...
//
//
// For distinct partitions, however, we use:
//
//     1 + x^k.
//
// Thus, the part k may appear:
//
//     zero times
//
// or:
//
//     once.
//
// This small change in the generating function
// expresses exactly the restriction that the parts
// must be distinct.
//
//
//
// Compare p(n) and q(n)
//
// For example:
//
//     p(5) = 7
//
// because:
//
//     5
//     4 + 1
//     3 + 2
//     3 + 1 + 1
//     2 + 2 + 1
//     2 + 1 + 1 + 1
//     1 + 1 + 1 + 1 + 1.
//
//
//
// But:
//
//     q(5) = 3
//
// because only:
//
//     5
//     4 + 1
//     3 + 2
//
// use distinct parts.
//
// Therefore:
//
//     q(n) <= p(n)
//
// for every n.
//
//
//
// A curious fact
//
// There is a beautiful theorem due to Euler:
//
//     The number of partitions of n into distinct
//     parts equals the number of partitions of n
//     into odd parts.
//
// For example, the partitions of 7 into distinct
// parts are:
//
//     7
//     6 + 1
//     5 + 2
//     4 + 3
//     4 + 2 + 1.
//
// There are five.
//
// The partitions of 7 using only odd parts are:
//
//     7
//     5 + 1 + 1
//     3 + 3 + 1
//     3 + 1 + 1 + 1 + 1
//     1 + 1 + 1 + 1 + 1 + 1 + 1.
//
// Again, there are five.
//
// The two sets of partitions look quite different,
// but they always have the same size.
//
//
//
// What about the algorithm?
//
// Just as with our previous recurrence for p(n),
// this direct recursive implementation repeats a
// tremendous amount of work.
//
// To calculate:
//
//     q(n),
//
// we recursively request:
//
//     q(n - 1)
//     q(n - 2)
//     q(n - 3)
//     ...
//     q(0).
//
// But each of those calculations recursively
// requests many of the same values again.
//
//
//
// For example, calculating q(10) requests:
//
//     q(9), q(8), q(7), ..., q(0).
//
// Calculating q(9) then requests:
//
//     q(8), q(7), q(6), ..., q(0)
//
// AGAIN.
//
// Calculating q(8) requests many of them yet again.
//
// Thus, the recursion tree contains enormous
// duplication.
//
//
//
// Memoization
//
// Once again, suppose we calculate:
//
//     q(8) = 6.
//
// Rather than recalculating q(8) every time it is
// needed, we could store:
//
//     q(8) -> 6.
//
// Every later request for q(8) could simply return
// the stored value.
//
// This is:
//
//     memoization.
//
//
//
// Alternatively, we could calculate:
//
//     q(0)
//     q(1)
//     q(2)
//     ...
//     q(n)
//
// in that order, storing each answer in an array.
//
// When calculating q(k), all the smaller values:
//
//     q(0), q(1), ..., q(k - 1)
//
// would already be available.
//
// This is the bottom-up form of:
//
//     dynamic programming.
//
//
//
// There is another repeated calculation
//
// Our implementation also repeatedly calculates:
//
//     sigma_1(k).
//
// These values depend only on k.
//
// Thus, if we were seriously interested in making
// this program efficient, we could also calculate:
//
//     sigma_1(1),
//     sigma_1(2),
//     ...
//     sigma_1(n)
//
// once and store them.
//
// This illustrates an important principle:
//
//     If the same deterministic calculation is
//     performed repeatedly with the same arguments,
//     consider storing its result.
//
//
//
// Questions:
//
// 1. What is the difference between p(n) and q(n)?
//
// 2. Why is q(0) defined to equal 1?
//
// 3. List all partitions of 6 into distinct parts.
//
// 4. Why does:
//
//        (1 + x)(1 + x^2)(1 + x^3)...
//
//    generate partitions into distinct parts?
//
// 5. What does the choice of x^k from the factor:
//
//        (1 + x^k)
//
//    represent?
//
// 6. Why can the part k occur at most once?
//
// 7. What is sigma_1(6)?
//
// 8. In the recurrence, how should:
//
//        sigma_1(k/2)
//
//    be interpreted when k is odd?
//
// 9. Why can we NOT simply use C++ integer
//    division and evaluate:
//
//        sigma( k/2 )
//
//    for odd k?
//
// 10. Use the recurrence to calculate q(5).
//
// 11. Why must:
//
//        q(n) <= p(n)?
//
// 12. What surprising relationship exists between
//     partitions into distinct parts and partitions
//     into odd parts?
//
// 13. What repeated calculations make this direct
//     recursive implementation inefficient?
//
// 14. How could memoization improve the
//     implementation?
//
// 15. How could we calculate q(0) through q(n)
//     using a bottom-up approach?
//
//
//
// The mathematical recurrence gives us a correct
// recursive definition:
//
//               n
//             -----
//          1  \
//   q(n) = -   )   q(n - k)
//          n  /
//             -----
//              k = 1
//
//              * [sigma_1(k) - 2*sigma_1(k/2)].
//
// But, as with the ordinary partition function,
// translating a mathematical recurrence literally
// into recursive C++ does not necessarily produce
// an efficient algorithm.
//
// Once again, the important computational question
// is:
//
//     Are we repeatedly solving the same
//     subproblems?
//
// If the answer is yes, this is a strong indication
// that:
//
//     memoization
//
// or:
//
//     dynamic programming
//
// may provide a much better implementation.