#include <iostream>
#include <cassert>
#include <climits>

// Multinomial coefficients are the coefficients
// in the expansion of
//
//     (x1 + x2 + ... + xm)^n.
//
// In particular, the coefficient of
//
//     x1^n1 * x2^n2 * ... * xm^nm
//
// where
//
//     n1 + n2 + ... + nm = n
//
// is the multinomial coefficient
//
//     (       n       )
//     ( n1, n2, ..., nm )
//
//              n!
//     = -------------------.
//       n1! * n2! * ... * nm!
//
// There are two ways to calculate these
// coefficients.
//
// 1. The factorial formula above.
//
// 2. The recursive formula
//
//     M(n; n1, ..., nm)
//
//       = M(n - 1; n1 - 1, n2, ..., nm)
//       + M(n - 1; n1, n2 - 1, ..., nm)
//       + ...
//       + M(n - 1; n1, n2, ..., nm - 1).
//
// Terms with a negative exponent are omitted.
//
// The base case is
//
//     M(0; 0, ..., 0) = 1.
//
// Equivalently, if one exponent equals n
// and all other exponents are zero, the
// multinomial coefficient equals one.
//
// PROBLEM
//
// Implement the multinomial function using
// both definitions:
//
//   multinomial_iter() uses the factorial
//   formula.
//
//   multinomial_rec() uses the recursive
//   formula.
//
// The arguments are n, m, and an array
// containing the m exponents n1, ..., nm.
//
// All exponents must be non-negative and
// their sum must equal n.
//
// For example, binomial coefficients are
// a special case of multinomial coefficients:
//
//     binomial(n, k) = M(n; k, n - k).
//
// Assume that all intermediate calculations
// and final results fit in unsigned long.
//
// See:
// https://en.wikipedia.org/wiki/Multinomial_theorem

// Function declarations
int main();

unsigned long multinomial_iter(
    unsigned long       const n,
    unsigned long       const m,
    unsigned long       const powers[]
);

unsigned long multinomial_rec(
    unsigned long       const n,
    unsigned long       const m,
    unsigned long             powers[]
);

unsigned long factorial(
    unsigned long       const n
);

// Function definitions
int main() {
    unsigned long const n{ 9 };
    unsigned long const m{ 5 };
    unsigned long powers[m]{ 2, 3, 3, 1, 0 };

    std::cout << multinomial_iter( n, m, powers )
              << " == 5040" << std::endl;

    std::cout << multinomial_rec( n, m, powers )
              << " == 5040" << std::endl;

    // Both implementations should agree.
    assert(
        multinomial_iter( n, m, powers )
        == multinomial_rec( n, m, powers )
    );

    // Test a binomial coefficient.
    unsigned long binomial_powers[]{ 3, 2 };

    assert(
        multinomial_iter( 5, 2, binomial_powers ) == 10
    );
    assert(
        multinomial_rec( 5, 2, binomial_powers ) == 10
    );

    // Test the base case.
    unsigned long zero_powers[]{ 0, 0, 0 };

    assert(
        multinomial_iter( 0, 3, zero_powers ) == 1
    );
    assert(
        multinomial_rec( 0, 3, zero_powers ) == 1
    );

    // Test a coefficient equal to one.
    unsigned long single_power[]{ 0, 5, 0 };

    assert(
        multinomial_iter( 5, 3, single_power ) == 1
    );
    assert(
        multinomial_rec( 5, 3, single_power ) == 1
    );

    // The recursive function must restore
    // every array entry before returning.
    assert( powers[0] == 2 );
    assert( powers[1] == 3 );
    assert( powers[2] == 3 );
    assert( powers[3] == 1 );
    assert( powers[4] == 0 );

    return 0;
}

// Done for you.
unsigned long factorial(
    unsigned long const n
) {
    unsigned long result{ 1 };

    for ( unsigned long k{ 2 }; k <= n; ++k ) {
        assert( result <= ULONG_MAX/k );
        result *= k;
    }

    return result;
}

unsigned long multinomial_iter(
    unsigned long const n,
    unsigned long const m,
    unsigned long const powers[]
) {
    assert( m > 0 );
    assert( powers != nullptr );

    // Your implementation goes here.

    return 0;
}

unsigned long multinomial_rec(
    unsigned long const n,
    unsigned long const m,
    unsigned long       powers[]
) {
    assert( m > 0 );
    assert( powers != nullptr );

    // Your implementation goes here.

    return 0;
}

























// First hint:
//
// Sum the entries of the array and assert
// that their sum equals n.
//
// For the iterative implementation, begin
// with n! and divide the result by each
// of the factorials of the exponents.
//
// For the recursive implementation, if
// n == 0, all exponents must be zero,
// so return 1.
//
// Otherwise, if any exponent equals n,
// the coefficient is also one.
//
// For example, suppose n == 6 and
//
//     powers = {3, 2, 1}.
//
// The recursive formula requires
// calculating the following:
//
//     M(5; 2, 2, 1)
//     M(5; 3, 1, 1)
//     M(5; 3, 2, 0)
//
// You can use the array you were passed:
//
//   1. Subtract one from the kth entry.
//   2. Make the recursive call.
//   3. Add one back to the kth entry.
//
// Only subtract from a non-zero entry.
//
// Be sure to restore the original array
// after each recursive call.

























// Second hint:
//
// In the recursive implementation, begin
// with a result of zero.
//
// For each non-zero exponent:
//
//     --powers[k];
//
//     result += multinomial_rec(
//         n - 1, m, powers
//     );
//
//     ++powers[k];
//
// Return the accumulated result.
//
// Be careful not to subtract one from
// an exponent that is already zero.

























// Here is one solution:

/*
unsigned long multinomial_iter(
    unsigned long const n,
    unsigned long const m,
    unsigned long const powers[]
) {
    assert( m > 0 );
    assert( powers != nullptr );

    unsigned long sum{ 0 };
    unsigned long result{ factorial( n ) };

    for ( unsigned long k{ 0 }; k < m; ++k ) {
        assert( powers[k] <= n - sum );
        sum += powers[k];

        result /= factorial( powers[k] );
    }

    assert( sum == n );

    return result;
}

unsigned long multinomial_rec(
    unsigned long const n,
    unsigned long const m,
    unsigned long       powers[]
) {
    assert( m > 0 );
    assert( powers != nullptr );

    // Verify the precondition during testing.
    #ifndef NDEBUG
    unsigned long sum{ 0 };

    for ( unsigned long k{ 0 }; k < m; ++k ) {
        assert( powers[k] <= n - sum );
        sum += powers[k];
    }

    assert( sum == n );
    #endif

    // Base case.
    if ( n == 0 ) {
        return 1;
    }

    unsigned long result{ 0 };

    for ( unsigned long k{ 0 }; k < m; ++k ) {
        // A single non-zero exponent
        // equal to n gives coefficient 1.
        if ( powers[k] == n ) {
            return 1;
        }

        if ( powers[k] != 0 ) {
            --powers[k];

            unsigned long const term{
                multinomial_rec( n - 1, m, powers )
            };

            ++powers[k];

            assert( term <= ULONG_MAX - result );
            result += term;
        }
    }

    return result;
}
*/