{"code":"matmul_9","name":"Connected Points","description":"Cho lưới $3 × N$ điểm. Mỗi điểm có tối đa 8 điểm xung quanh.\r\n\r\n![enter image description here][1]\r\n\r\nNgười ta nối các điểm của lưới tạo thành một đường gấp khúc khép kín với các tính chất sau:\r\n\r\nĐường gấp khúc chứa tất cả $3 × N$ điểm của lưới.\r\nChỉ các đỉnh kề nhau mới được nối với nhau\r\nĐường gấp khúc không tự cắt\r\n\r\n![enter image description here][2]\r\n\r\nFigure 2: Ví dụ 2 cách nối với $N = 6$.\r\n\r\nHãy viết chương trình tính số cách nối thỏa mã các điều kiện trên. Chú ý in ra kết quả theo mô đun $1,000,000,000$.\r\n\r\n<h4>Input</h4>\r\n\r\n- Dòng duy nhất chứa số nguyên $N (N \\le 1,000,000,000)$.\r\n\r\n<h4>Output</h4>\r\n\r\n- Gồm một dòng duy nhất là số cách nối theo mô đun $1,000,000,000$.\r\n\r\n<h4>Example</h4>\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        8\r\n        ```\r\n\r\n!!! question \"Test 2\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        40\r\n        ```\r\n\r\n[1]: https://i.imgur.com/D6jbuaA.png\r\n\r\n[2]: https://i.imgur.com/4nWJnYg.png","points":300.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}