1947 선물 전달

#include <stdio.h>
 
long long dp[1000005] = { 0 };
 
int main() {
    int n;
    scanf("%d", &n);
 
    if (n == 1) {
        printf("0");
        return 0;
    }
    else if (n == 2) {
        printf("1");
        return 0;
    }
 
    dp[1] = 0;
    dp[2] = 1;
    for (int i = 3; i <= n; i++) {
        dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2])) % 1000000000;
    }
 
    printf("%lld", dp[n]);
}