Một hoán vị của ~N~ số nguyên dương đầu tiên là dãy số ~P_1, P_2, \ldots, P_n~ thoả mãn ~0 < P_i < N+1~ và ~P_i \ne P_j~ (với mọi ~i \ne j~). MH muốn đếm số hoán vị của ~N~ số nguyên dương đầu tiên thoả mãn ~P_i \ne i~ với mọi ~i=1..N~. Với trình độ toán cao siêu MH đã  tìm được cách tính ngắn gọn. Nhưng MH không phải là dân chuyên Tin nên bạn không thể tính được với ~N~ rất lớn. Bạn hãy giúp MH và chứng tỏ mình nhé.

Input

Gồm một số nguyên dương ~N~ ~\left(0 < N < 5001\right)~ duy nhất

Output

Gồm một số nguyên dương duy nhất là đáp số của bài toán sau khi ~mod~ ~76213~

Sample Input

3

Sample Output

2