#include <iostream>
#include <cassert>

// Binomial coefficients occur when you
// expand (x + y)^n. However, what happens
// when you expand the falling factorial
//
//     x(x - 1)(x - 2) ... (x - n + 1)?
//
// For example, if n = 5, we have
//
//     x(x - 1)(x - 2)(x - 3)(x - 4)
//
//       = x^5 - 10x^4 + 35x^3 - 50x^2 + 24x.
//
// The coefficients 1, -10, 35, -50, and 24
// are called the signed Stirling numbers of
// the first kind. We will encounter the
// Stirling numbers of the second kind in
// another tutorial.
//
// Suppose you are asked to calculate these
// numbers as part of a project during a
// co-op placement. You consult Abramowitz
// and Stegun, and on page 824 you find the
// following recurrence relation:
//
//     S(n + 1, m) = S(n, m - 1) - n*S(n, m).
//
// Here, S(n, m) denotes the coefficient of
// x^m in the expansion of
//
//     x(x - 1)(x - 2) ... (x - n + 1).
//
// Unfortunately, the reference does not
// immediately tell you which base cases
// you need to implement the recursion.
//
// You might consult Wikipedia to find
// these base cases.
//
// Use the recurrence relation and the
// appropriate base cases to implement a
// function that calculates the signed
// Stirling numbers of the first kind.
//
// Assume n >= 0 and m >= 0. If m > n,
// the function should return zero.

  /////////////////
 // APPLICATION //
/////////////////

// The absolute value of the Stirling number
// of the first kind, |S(n, m)|, counts the
// number of permutations of n distinct
// objects having exactly m disjoint cycles.
//
// For example, four distinct objects
// A, B, C, and D can be arranged into
// exactly two cycles in eleven ways.
//
// Three arrangements have two cycles
// of length two:
//
//     (A B)(C D)
//     (A C)(B D)
//     (A D)(B C)
//
// Eight arrangements have one cycle of
// length three and one fixed point:
//
//     (A B C)(D)
//     (A C B)(D)
//
//     (A B D)(C)
//     (A D B)(C)
//
//     (A C D)(B)
//     (A D C)(B)
//
//     (B C D)(A)
//     (B D C)(A)
//
// The order in which cycles are written
// does not matter. Rotating the elements
// within a cycle also gives the same cycle.
//
// Consequently,
//
//     |S(4, 2)| = 11.
//
// Note that reversing a cycle of length
// three generally produces a different
// permutation.

// Function declarations
int main();

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

// Function definitions
int main() {
    // Print the coefficients of the
    // falling factorial for n = 5,
    // starting with the constant term.

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

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

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

    // Test some known values.
    assert( stirling_first( 4, 2 ) == 11 );
    assert( stirling_first( 5, 1 ) == 24 );
    assert( stirling_first( 5, 2 ) == -50 );
    assert( stirling_first( 5, 3 ) == 35 );
    assert( stirling_first( 5, 4 ) == -10 );
    assert( stirling_first( 5, 5 ) == 1 );

    return 0;
}

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

    // Your implementation goes here.

    return 0;
}

























// First hint:
//
// You will find that
//
//     S(0, 0) = 1,
//
// while
//
//     S(n, 0) = 0  for n > 0,
//     S(0, m) = 0  for m > 0.
//
// In addition, S(n, m) = 0 if m > n.
//
// The recurrence relation is given 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) = S(n - 1, m - 1)
//               - (n - 1)*S(n - 1, m).
//
// Use this recurrence when n > 0 and
// 1 <= m <= n.

























// Here is one solution:

/*
long stirling_first(
    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 stirling_first( n - 1, m - 1 )
            - (n - 1)*stirling_first( n - 1, m );
    }
}
*/