Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKPATROL - Robot tuần tra

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkpatrol


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 kích thước 3x3 và 6 cách đi trên sân

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


Được gửi lên bởi:Alex & Friends
Ngày:2012-11-16
Thời gian chạy:2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Trần Anh Hướng Thái Huy

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.