#include <iostream>
#include <cassert>

// Stirling numbers of the first kind are
// the coefficients obtained by expanding
// the falling factorial
//
//     x(x - 1)(x - 2) ... (x - n + 1).
//
// The absolute values of these coefficients
// also count the number of permutations of
// n distinct objects having exactly m cycles.
//
// Stirling numbers of the second kind count
// the number of ways to partition n distinct
// objects into m non-empty, disjoint subsets.
//
// The subsets are unlabelled: changing the
// order in which they are listed does not
// produce a different partition.
//
// For example, five distinct objects
// A, B, C, D, and E can be partitioned
// into three non-empty subsets as follows.
//
// First, there are ten partitions consisting
// of one subset of size three and two
// subsets of size one:
//
//     {A, B, C}, {D}, {E}
//     {A, B, D}, {C}, {E}
//     {A, B, E}, {C}, {D}
//     {A, C, D}, {B}, {E}
//     {A, C, E}, {B}, {D}
//     {A, D, E}, {B}, {C}
//     {B, C, D}, {A}, {E}
//     {B, C, E}, {A}, {D}
//     {B, D, E}, {A}, {C}
//     {C, D, E}, {A}, {B}
//
// There are also fifteen partitions
// consisting of two subsets of size two
// and one subset of size one:
//
//     {A, B}, {C, D}, {E}
//     {A, B}, {C, E}, {D}
//     {A, B}, {D, E}, {C}
//     {A, C}, {B, D}, {E}
//     {A, C}, {B, E}, {D}
//     {A, C}, {D, E}, {B}
//     {A, D}, {B, C}, {E}
//     {A, D}, {B, E}, {C}
//     {A, D}, {C, E}, {B}
//     {A, E}, {B, C}, {D}
//     {A, E}, {B, D}, {C}
//     {A, E}, {C, D}, {B}
//     {B, C}, {D, E}, {A}
//     {B, D}, {C, E}, {A}
//     {B, E}, {C, D}, {A}
//
// Consequently, there are 25 partitions,
// and the Stirling number of the second
// kind is
//
//     S(5, 3) = 25.
//
// These numbers satisfy the recurrence
//
//     S(n + 1, m) = m*S(n, m) + S(n, m - 1).
//
// To understand this recurrence, consider
// adding one new object to a partition
// of n objects into m subsets.
//
// Either the new object joins one of the
// m existing subsets, or it forms a new
// subset containing only itself.
//
// In the first case, there are m choices
// of an existing subset. In the second
// case, the original n objects must be
// partitioned into m - 1 subsets.
//
// Use this recurrence and the appropriate
// base cases to implement a function that
// calculates Stirling numbers of the
// second kind.
//
// Assume n >= 0 and m >= 0. If m > n,
// the function should return zero.

// Function declarations
int main();

long stirling_second(
    long const n,
    long const m
);

// Function definitions
int main() {
    // Print S(5, m) for m = 0, ..., 5.

    for ( long m{ 0 }; m <= 5; ++m ) {
        std::cout << stirling_second( 5, m )
                  << std::endl;
    }

    // Test the base cases.
    assert( stirling_second( 0, 0 ) == 1 );
    assert( stirling_second( 5, 0 ) == 0 );
    assert( stirling_second( 0, 5 ) == 0 );

    // Test the case m > n.
    assert( stirling_second( 3, 4 ) == 0 );

    // Test some known values.
    assert( stirling_second( 4, 2 ) == 7 );
    assert( stirling_second( 5, 1 ) == 1 );
    assert( stirling_second( 5, 2 ) == 15 );
    assert( stirling_second( 5, 3 ) == 25 );
    assert( stirling_second( 5, 4 ) == 10 );
    assert( stirling_second( 5, 5 ) == 1 );

    return 0;
}

long stirling_second(
    long const n,
    long const m
) {
    assert( n >= 0 );
    assert( m >= 0 );

    // Your implementation goes here.

    return 0;
}

























// First hint:
//
// If n = m = 0, there is exactly one
// partition of the empty set into
// zero subsets:
//
//     S(0, 0) = 1.
//
// However, a non-empty set cannot be
// partitioned into zero non-empty subsets,
// and the empty set cannot be partitioned
// into a positive number of non-empty
// subsets.
//
// Therefore,
//
//     S(n, 0) = 0  for n > 0,
//     S(0, m) = 0  for m > 0.
//
// Also, S(n, m) = 0 whenever m > n.
//
// The recurrence relation is expressed
// in terms of S(n + 1, m), but your
// function is passed n.
//
// Rewrite the recurrence relation to
// calculate S(n, m) instead.

























// Second hint:
//
// The rewritten recurrence relation is
//
//     S(n, m) = m*S(n - 1, m)
//               + S(n - 1, m - 1).
//
// Use this recurrence when n > 0 and
// 1 <= m <= n.

























// Here is one solution:

/*
long stirling_second(
    long const n,
    long const m
) {
    assert( n >= 0 );
    assert( m >= 0 );

    if ( n == 0 && m == 0 ) {
        return 1;
    } else if ( n == 0 || m == 0 || m > n ) {
        return 0;
    } else {
        return m*stirling_second( n - 1, m )
             + stirling_second( n - 1, m - 1 );
    }
}
*/