{"code":"lqdojcontest8bai3","name":"LQDOJ Contest #8 - Bài 3 - Hoán Vị","description":"[user:shiba] - bạn thân của [user:_minhduc] trong khi làm bài tập tết để vào ngày mùng tết cậu ấy có thể đi chơi thoải mái thì gặp một bài từ rất khó từ thầy giáo: Cho một số nguyên dương $N$. Một dãy được gọi là dãy đẹp khi dãy đó là hoán vị của các số từ $1$ đến $N$ và dãy đó thỏa mãn rằng có ít nhất một cặp số liền kề trong dãy đó có dạng $(x,x+1)$. Ví dụ với $N = 4$ thì các dãy $(1,2,4,3)$ và $(3,4,1,2)$ là các dãy đẹp, còn các dãy $(3,1,4,2)$ và $(4,3,2,1)$ thì không phải. [user:shiba] cần đếm số dãy đẹp khác nhau có thể tạo ra khi biết trước số nguyên dương $N$.\r\n\r\nBài này khó đến nổi [user:shiba] không làm được. Cậu ấy chợt nhớ nhớ ra rằng [user:_minhduc] rất thông thạo về dãy hoán vị nên [user:shiba] đã hỏi bài bạn thân của mình. Nhưng [user:_minhduc] đang bận chơi game \"bình nguyên vô tận\" với bạn gái nên không thể chỉ bài cho [user:shiba] được vì sợ nếu bỏ trận đấu giữa chừng thì bạn gái của mình sẽ giận. Vì vậy [user:_minhduc] nhờ các bạn tài giỏi trong **LQDOJ** giải quyết bài toán này cho [user:shiba] ~rồi [user:_minhduc] sẽ lì xì cho các bạn :Đ~\r\n\r\n**Yêu cầu:** Bạn hãy viết chương trình giải quyết bài toán trên sau khi chia lấy dư cho $M$ với $M$ là một số nguyên dương được nhập từ bàn phím.\r\n\r\n#### Input\r\n\r\n - Chứa hai số nguyên dương lần lượt là $N$ và $M$ $(1 \\le N \\le 10^{18}, 2 \\le M \\le 10^7)$.\r\n\r\n#### Output \r\n\r\n - In ra kết quả bài toán sau khi chia lấy dư cho $M$.\r\n\r\n#### Scoring\r\n\r\n - Subtask $1$ ($10\\%$ số điểm): Có $N \\le 10$.\r\n\r\n - Subtask $2$ ($20\\%$ số điểm): Có $N \\le 15$.\r\n\r\n - Subtask $3$ ($20\\%$ số điểm): Có $N \\le 20$.\r\n\r\n - Subtask $4$ ($30\\%$ số điểm): Có $N \\le 10^6$.\r\n\r\n - Subtask $5$ ($20\\%$ số điểm): Không có ràng buộc gì thêm.\r\n \r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4 100\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        13\r\n        ```\r\n    ??? warning \"Note\"\r\n        - Có $13$ dãy đẹp:\r\n            - $1: (1,2,3,4)$\r\n            - $2: (1,2,4,3)$\r\n            - $3: (1,3,4,2)$\r\n            - $4: (1,4,2,3)$\r\n            - $5: (2,1,3,4)$\r\n            - $6: (2,3,1,4)$\r\n            - $7: (2,3,4,1)$\r\n            - $8: (3,1,2,4)$\r\n            - $9: (3,4,1,2)$\r\n            - $10: (3,4,2,1)$\r\n            - $11: (4,1,2,3)$\r\n            - $12: (4,2,3,1)$\r\n            - $13: (4,3,1,2)$","points":1900.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}}