Q623: 500!

/*
    上傳時再改成 LEN: 2600, N: 1000
    用上一個的結果去算就不會TLE了

    Run time: 0.410
*/
#include <stdio.h>
#define LEN 2600
#define N 1000

int arr[N+1][LEN];
void calculate();

int main()
{
    int n;
    int i;

    calculate();

    while (scanf("%d", &n) != EOF)
    {
        printf("%d!\n", n);

        for ( i = LEN-1; i >= 0; i--)
            if (arr[n][i])
                break;

        for ( ; i >= 0; i--)
            printf("%d", arr[n][i]);
        printf("\n");
    }

    return 0;
}

void calculate()
{
    int i, j;

    // initial value: 0! = 1, 1! = 1
    arr[0][0] = 1, arr[1][0] = 1;

    for ( i = 2; i <= N; i++)
    {
        for ( j = 0; j < LEN; j++)
        {
            arr[i][j] += arr[i-1][j] * i;

            // to calculate carry
            if (arr[i][j] >= 10)
            {
                arr[i][j+1] += arr[i][j]/10;
                arr[i][j] %= 10;
            }
        }
    }
}