#include <cassert>
#include <iostream>

// Discovering the growth of a recurrence
//
// We have already considered:
//
//     T(n) = T(n - 1) + 1
//
// which grows linearly:
//
//     Theta(n),
//
// and:
//
//     T(n) = T(n - 1) + n
//
// which grows quadratically:
//
//     Theta(n^2).
//
// Now consider a very different recurrence:
//
//             /
//            (   0                    n = 1
//             )
//     T(n) = <
//             )
//            (   n*T(n - 1) + n      n > 1.
//             \
//
// Author the function T(n), asserting that:
//
//     n >= 1.
//
// Then, in main(), write a loop that calculates:
//
//     T(1), T(2), T(3), ...
//
// Try to determine how quickly T(n) grows.
//
// You may not be able to immediately recognize an
// exact formula.
//
// Instead, compare the values with another function
// that grows very quickly:
//
//     n!

// Function declarations
int main();

unsigned long long T(
    unsigned int const n
);

// Function definitions
int main() {
    // Your implementation here.

    return 0;
}


// unsigned long long T( ... )
//
// @param n
//     A positive integer.
//
// @returns
//     The value defined recursively by:
//
//         T(1) = 0
//
//     and:
//
//         T(n) = n*T(n - 1) + n
//
//     for n > 1.

unsigned long long T(
    unsigned int const n
) {
    assert( n >= 1 );

    // Your implementation here.

    return 0;
}














































// Hint
//
// Begin by printing:
//
//     T(1)
//     T(2)
//     T(3)
//     ...
//
// For example:
//
//     for ( unsigned int k{ 1 };
//           k <= 10;
//           ++k ) {
//         std::cout << "T(" << k << ") = "
//                   << T( k )
//                   << std::endl;
//     }
//
// What do you notice about how quickly the values
// grow?
//
// If the pattern is not obvious, compare T(n) with:
//
//     n!
//
// for the same values of n.














































// Solution

/*
int main() {
    for ( unsigned int k{ 1 };
          k <= 10;
          ++k ) {
        std::cout << "T(" << k << ") = "
                  << T( k )
                  << std::endl;
    }

    return 0;
}

unsigned long long T(
    unsigned int const n
) {
    assert( n >= 1 );

    if ( n == 1 ) {
        return 0;
    } else {
        return n*T( n - 1 ) + n;
    }
}
*/














































// What is the pattern?
//
// Here is the output:
//
//                                      n!
//
//     T(1)  =       0                  1
//     T(2)  =       2                  2
//     T(3)  =       9                  6
//     T(4)  =      40                 24
//     T(5)  =     205                120
//     T(6)  =    1236                720
//     T(7)  =    8659               5040
//     T(8)  =   69280              40320
//     T(9)  =  623529             362880
//     T(10) = 6235300            3628800
//
//
// The recurrence itself explains why these values
// become so large.
//
// Consider:
//
//     T(10) = 10*T(9) + 10.
//
// We do not merely add some work to T(9).
//
// We require TEN copies of the work represented by
// T(9), followed by some additional work.
//
// Similarly:
//
//     T(9) = 9*T(8) + 9,
//
//     T(8) = 8*T(7) + 8,
//
// and so on.
//
//
//
// Compare our three recurrences
//
// First:
//
//     T(n) = T(n - 1) + 1.
//
// At each level:
//
//     one smaller problem
//
//         +
// 
//     one additional operation.
//
// This gives:
//
//     Theta(n).
//
//
// Second:
//
//     T(n) = T(n - 1) + n.
//
// At each level:
//
//     one smaller problem
//
//         +
//
//     n additional operations.
//
// This gives:
//
//     Theta(n^2).
//
//
// Now:
//
//     T(n) = n*T(n - 1) + n.
//
// At each level:
//
//     n smaller problems
//
//         +
//
//     n additional operations.
//
// This is dramatically different.
//
//
//
// Why factorial?
//
// Ignore the final +n for a moment.
//
// We have approximately:
//
//     T(n) = n*T(n - 1).
//
// Then:
//
//     T(n)
//       approximately n*(n - 1)*T(n - 2)
//
//       approximately n*(n - 1)*(n - 2)*T(n - 3)
//
//       ...
//
// The products:
//
//     n*(n - 1)*(n - 2)*...
//
// should look familiar.
//
// They are producing a factorial.
//
// This suggests that:
//
//     T(n)
//
// grows at approximately the same rate as:
//
//     n!
//
// and indeed:
//
//     T(n) = Theta(n!).
//
//
//
// An exact formula
//
// You are NOT expected to derive the following
// formula in this course.
//
// It is included only to show that the recurrence
// can, in fact, be solved exactly.
//
// Begin with:
//
//     T(n) = n*T(n - 1) + n.
//
// Divide both sides by n!:
//
//     T(n)          T(n - 1)       1
//     -----   =     --------   +  -----.
//      n!             (n-1)!       (n-1)!
//
// Define:
//
//             T(n)
//     S(n) = ------.
//              n!
//
// Then:
//
//     S(n) = S(n - 1) + 1/(n - 1)!.
//
// Since:
//
//     S(1) = 0,
//
// we obtain:
//
//                n - 1
//                -----
//                 \       1
//     S(n) =       )     ---.
//                 /       k!
//                -----
//                 k = 1
//
// Therefore:
//
//                       n - 1
//                       -----
//                        \       1
//     T(n) = n!          )     ---.
//                        /       k!
//                       -----
//                        k = 1
//
//
//
// There is also a famous infinite series:
//
//                 infinity
//                  -----
//                   \       1
//     e =            )     ---.
//                   /       k!
//                  -----
//                   k = 0
//
// Thus:
//
//                 infinity
//                  -----
//                   \       1
//     e - 1 =        )     ---.
//                   /       k!
//                  -----
//                   k = 1
//
// Our finite sum approaches:
//
//     e - 1.
//
// Therefore, for large n:
//
//     T(n) is approximately (e - 1)*n!.
//
// Since:
//
//     e - 1 is approximately 1.71828,
//
// we expect:
//
//     T(n)
//
// to be approximately:
//
//     1.71828*n!.
//
//
//
// For example:
//
//     T(10) = 6235300
//
// while:
//
//     10! = 3628800.
//
// Their ratio is approximately:
//
//     1.718.
//
// This is not a coincidence.
//
//
//
// The important result for this course
//
// You do NOT need the exact formula:
//
//                       n - 1
//                       -----
//                        \       1
//     T(n) = n!          )     ---.
//                        /       k!
//                       -----
//                        k = 1
//
// The important observation is:
//
//     T(n) = Theta(n!).
//
// Factorial growth is extraordinarily fast.
//
//
//
// Where might such a recurrence occur?
//
// Consider the cofactor expansion for calculating
// the determinant of an n by n matrix.
//
// Let A be an n by n matrix.
//
// Let:
//
//     A_(1,j)
//
// be the (n - 1) by (n - 1) matrix obtained by
// deleting Row 1 and Column j.
//
// Expanding the determinant along the first row:
//
//     det(A)
//
//       = a_(1,1) det(A_(1,1))
//
//         - a_(1,2) det(A_(1,2))
//
//         + a_(1,3) det(A_(1,3))
//
//         - ...
//
//         + (-1)^(n+1) a_(1,n) det(A_(1,n)).
//
//
//
// Look at what this algorithm requires.
//
// To calculate the determinant of an n by n matrix,
// we must calculate:
//
//     n
//
// determinants of matrices of size:
//
//     (n - 1) by (n - 1).
//
// We also perform approximately n multiplications.
//
// Thus, a simplified recurrence for the number of
// multiplications is:
//
//     T(n) = n*T(n - 1) + n.
//
//
//
// A recursion tree
//
// At the top:
//
//                        n
//
// there are n recursive determinant calculations:
//
//                /   /   |   \   \
//
//              n-1 n-1  ...  n-1
//
//
// Each of THOSE creates n - 1 recursive calls:
//
//             /  /  |  \
//            /  /   |   \
//
//          n-2 n-2 ... n-2
//
//
// The number of recursive calculations grows
// approximately like:
//
//     n
//
//     n*(n - 1)
//
//     n*(n - 1)*(n - 2)
//
//     ...
//
//     n!
//
// This is why the algorithm becomes impractical
// extraordinarily quickly.
//
//
//
// What about a 30 by 30 matrix?
//
// We know:
//
//     T(n) is approximately (e - 1)*n!.
//
// Thus:
//
//     T(30)
//
// is approximately:
//
//     (e - 1)*30!.
//
// This is approximately:
//
//     4.56 x 10^32
//
// multiplications.
//
// That is:
//
//     455779168962082450381327904693700
//
// multiplications.
//
//
//
// Suppose you had an extraordinarily fast computer
//
// Imagine a computer capable of performing:
//
//     10^15
//
// floating-point operations every second.
//
// This is one petaflop.
//
// The required time would be approximately:
//
//         4.56 x 10^32
//         -----------
//           10^15
//
//       = 4.56 x 10^17 seconds.
//
// Converting to years gives approximately:
//
//     14.4 billion years.
//
// This is on the same scale as the age of the
// universe.
//
//
//
// Now compare that with a better algorithm.
//
// Standard determinant algorithms based on Gaussian
// elimination require work proportional to:
//
//     n^3.
//
// For n = 30:
//
//     30^3 = 27000.
//
// Compare:
//
//     approximately 4.56 x 10^32
//
// with:
//
//     fewer than a modest constant times 27000.
//
// The difference is almost absurd.
//
//
//
// This illustrates why algorithm analysis matters.
//
// Two algorithms may produce exactly the same
// mathematical answer.
//
// That does NOT mean they are equally useful.
//
// For small values of n, an inefficient algorithm
// may appear perfectly reasonable.
//
// As n grows:
//
//     Theta(n)
//
//     Theta(n^2)
//
//     Theta(n^3)
//
//     Theta(n!)
//
// behave very differently.
//
//
//
// A rough comparison
//
//     n        n       n^2       n^3          n!
//
//     5        5        25       125          120
//
//     10      10       100      1000      3628800
//
//     20      20       400      8000     2.43x10^18
//
//     30      30       900     27000     2.65x10^32
//
//
// Factorial growth rapidly overwhelms polynomial
// growth.
//
//
//
// Questions:
//
// 1. What values do you obtain for T(1) through
//    T(10)?
//
// 2. Why does this recurrence grow much faster than:
//
//        T(n) = T(n - 1) + n?
//
// 3. What product begins to appear if you repeatedly
//    expand:
//
//        T(n) = n*T(n - 1) + n?
//
// 4. Why does this suggest factorial growth?
//
// 5. What does:
//
//        T(n) = Theta(n!)
//
//    tell us about the growth of this recurrence?
//
// 6. In a cofactor expansion, how many determinants
//    of size (n - 1) by (n - 1) must be calculated?
//
// 7. Why does recursively applying cofactor
//    expansion lead to factorial growth?
//
// 8. Approximately how many multiplications are
//    described by this recurrence for n = 30?
//
// 9. Why is an algorithm requiring approximately
//    n^3 operations dramatically preferable for
//    calculating large determinants?
//
//
//
// Our progression is now:
//
//     T(n) = T(n - 1) + 1
//
//              Theta(n)
//
//                 |
//                 v
//
//     T(n) = T(n - 1) + n
//
//              Theta(n^2)
//
//                 |
//                 v
//
//     T(n) = n*T(n - 1) + n
//
//              Theta(n!)
//
//
// A small change in a recurrence can represent an
// enormous change in the amount of work performed
// by an algorithm.
//
// This is one of the principal reasons we analyze
// algorithms rather than merely observing that they
// produce the correct answer.