Trong một bữa tối, có 𝑛 giáo sư ngồi trong một căn phòng lớn. Các giáo sư được đánh số từ 1 đến 𝑛 từ người cao tuổi nhất tới người ít tuổi nhất. Lần lượt từng giáo sư sẽ cầm đũa lên, tuy nhiên để thể hiện sự tôn trọng của bề dưới đối với bề trên, thứ tự cầm đũa sẽ phải thỏa mãn quy tắc sau: Giáo sư 1 sẽ cầm đũa đầu tiên. Giáo sư 𝑖 (𝑖 = 2,3,,𝑛) chỉ được phép cầm đũa khi giáo sư 𝑖 1 hoặc giáo sư 𝑖 2 đã cầm đũa. Ví dụ: (1, 3, 5, 4, 2) là một thứ tự cầm đũa hợp lệ. (1, 2, 5, 3, 4) là một thứ tự cầm đũa không hợp lệ (giáo sư 5 đã vi phạm nguyên tắc khi cầm đũa trước giáo sư 3 và giáo sư 4). (2, 1, 3, 4, 5) là một thứ tự cầm đũa không hợp lệ (giáo sư 1 phải là người cầm đũa đầu tiên). Yêu cầu: Gọi Q là số cách thứ tự cầm đũa thỏa mãn quy tắc đặt ra. Hãy tính Q. Input: Vào từ tệp Dinner.inp · Chứa một số nguyên dương 𝑛 106; Output: Ghi ra tệp Dinner.out · Một số nguyên duy nhất Q là số dư của phép chia kết quả tìm được cho 109 + 7. Ví dụ: Dinner.inp 3 Dinner.out 2 Dinner.inp 5 Dinner.out 10 Ràng Buộc: 50% số test có 𝑛 10; giải c++