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

Một cái sân hình vuông có cạnh N (đơn vị độ dài). Các hàng (cột) của sân được đánh số từ 1-->N. Sân được chia thành N^2 ô vuông đơn vị. Ô tại hàng i cột j có tên là (i,j). Trên sân chỉ cho phép đi ngang hoặc dọc (nhưng có thể di chuyển nhiều ô 1 lúc). Vào buổi tối, người ta dùng một con Robot để canh gác.

Ban đầu Robot được đặt tại một ô bất kì. Sau đó Robot sẽ tự chọn ra một đường đi trên sân và sẽ lặp lại đường đi đó cho đến sáng. Vì thế, Robot đã được lặp trình thỏa một số điều kiện:

- Để cho việc lặp lại đường đi, điểm đầu phải trùng với điểm cuối.

- Để đảm bảo an toàn, Robot phải đi trên tất cả các hàng và các cột.

- Để tiết kiệm, Robot không được đi quá một lần trên một hàng hoặc một cột.

Ta nói Robot đi trên một hàng (hoặc cột) là khi Robot đi giữa hai ô nằm trên cùng một hàng (hoặc cột). Có thể trong lúc đi chuyển Robot sẽ cắt với một hàng (hoặc cột) tại đúng một ô nào đó, nhưng ta không gọi đó là đi trên hàng (hoặc cột).

Ví dụ: N=4, di chuyển ngang từ ô (2,1) đến (2,4) thì:

+ Robot đi trên hàng số 2.

+ Đường đi có cắt cột số 3 tại ô (2,3), nhưng đây không được gọi là đi trên cột số 3.

Yêu cầu: Đếm số dạng đường đi có thể. Biết hai dạng đường đi gọi là khác nhau nếu hình vẽ của chúng trên sân là khác nhau.

Giới hạn:

_ N<=1000000000

_ 40% test có N<=1000

_ 80% test có N<=1000000

Input

_ Dòng duy nhất là số N - kích thước của sân.

Output

_ Cho biết số dạng đường đi có thể trên sân. Do kết quả có thể rất lớn, hãy in phần dư khi chia kết quả cho 939999953.

Example

Input:
3

Output:
6

Giải thích: có 6 cách đi
1. (1,1) --> (1,3) --> (2,3) --> (2,2) --> (3,2) --> (3,1) --> (1,1)
2. (1,1) --> (1,3) --> (3,3) --> (3,2) --> (2,2) --> (2,1) --> (1,1)
3. (1,1) --> (1,2) --> (2,2) --> (2,3) --> (3,3) --> (3,1) --> (1,1)
4. (1,2) --> (1,3) --> (3,3) --> (3,1) --> (2,1) --> (2,2) --> (1,2)
5. (1,1) --> (1,2) --> (3,2) --> (3,3) --> (2,3) --> (2,1) --> (1,1)
6. (1,2) --> (1,3) --> (2,3) --> (2,1) --> (3,1) --> (3,2) --> (1,2)
Ta có (3,3) --> (1,3) --> (1,2) --> (2,2) --> (2,1) --> (3,1) --> (3,3) 
cũng là một đường đi đúng, nhưng hình vẽ của nó đã trùng với hình của đường số 4.

Sân N=3 và 6 dạng đường đi (xem mỗi ô trên sân là 1 chấm đỏ).