Giải bài trực tuyến

Một hoán vị của N số nguyên dương đầu tiên là dãy số P1,P2,...,Pn thoả mãn 0Pj (với mọi i<>j). MH muốn đếm số hoán vị của N số nguyên dương đầu tiên thoả mãn Pi<>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 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

Example

Input:
3

Output:
2

Constraint

0