Robot tuần tra

Xem dạng PDF

Gửi bài giải


Điểm: 0,64 (OI)
Giới hạn thời gian: 3.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
Trần Anh Hướng Thái Huy
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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 ~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à ~\left(i,j\right)~. 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ừ ô ~\left(2,1\right)~ đến ~\left(2,4\right)~ thì:

  • Robot đi trên hàng số ~2~.
  • Đường đi có cắt cột số ~3~ tại ô ~\left(2,3\right)~, 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.

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~.

Giới hạn

  • ~N \le 1000000000~
  • ~40\%~ test có ~N \le 1000~
  • ~80\%~ test có ~N \le 1000000~

Sample Input

3

Sample Output

6

Note

Giải thích: có ~6~ cách đi

  1. ~(1~, ~1)~ ~\rightarrow~ ~(1~, ~3)~ ~\rightarrow~ ~(2~, ~3)~ ~\rightarrow~ ~(2~, ~2)~ ~\rightarrow~ ~(3~, ~2)~ ~\rightarrow~ ~(3~, ~1)~ ~\rightarrow~ ~(1~, ~1)~
  2. ~(1~, ~1)~ ~\rightarrow~ ~(1~, ~3)~ ~\rightarrow~ ~(3~, ~3)~ ~\rightarrow~ ~(3~, ~2)~ ~\rightarrow~ ~(2~, ~2)~ ~\rightarrow~ ~(2~, ~1)~ ~\rightarrow~ ~(1~, ~1)~
  3. ~(1~, ~1)~ ~\rightarrow~ ~(1~, ~2)~ ~\rightarrow~ ~(2~, ~2)~ ~\rightarrow~ ~(2~, ~3)~ ~\rightarrow~ ~(3~, ~3)~ ~\rightarrow~ ~(3~, ~1)~ ~\rightarrow~ ~(1~, ~1)~
  4. ~(1~, ~2)~ ~\rightarrow~ ~(1~, ~3)~ ~\rightarrow~ ~(3~, ~3)~ ~\rightarrow~ ~(3~, ~1)~ ~\rightarrow~ ~(2~, ~1)~ ~\rightarrow~ ~(2~, ~2)~ ~\rightarrow~ ~(1~, ~2)~
  5. ~(1~, ~1)~ ~\rightarrow~ ~(1~, ~2)~ ~\rightarrow~ ~(3~, ~2)~ ~\rightarrow~ ~(3~, ~3)~ ~\rightarrow~ ~(2~, ~3)~ ~\rightarrow~ ~(2~, ~1)~ ~\rightarrow~ ~(1~, ~1)~
  6. ~(1~, ~2)~ ~\rightarrow~ ~(1~, ~3)~ ~\rightarrow~ ~(2~, ~3)~ ~\rightarrow~ ~(2~, ~1)~ ~\rightarrow~ ~(3~, ~1)~ ~\rightarrow~ ~(3~, ~2)~ ~\rightarrow~ ~(1~, ~2)~

Ta có ~(3~, ~3)~ ~\rightarrow~ ~(1~, ~3)~ ~\rightarrow~ ~(1~, ~2)~ ~\rightarrow~ ~(2~, ~2)~ ~\rightarrow~ ~(2~, ~1)~ ~\rightarrow~ ~(3~, ~1)~ ~\rightarrow~ ~(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.

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


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.