Táo quân ngoại truyện(Ep.3 bản dễ)

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Hôm nay, các táo đang chuẩn bị cho trận đá bóng căng nhất lịch sử với các thiên đình khác. Các thành viên gồm: Táo kinh tế: dang7rickroll, táo y tế: phanhuykhang, táo mạng: nguyenminhhai021009, táo giao thông: stack_queue_4977, táo nông nghiệp: huyhau6a2, ...(Tên viết trong đây là hư cấu hehe)

Trước sự kiện này, ngọc hoàng đã tạo ra \(1\) thử thách để luyện tập cho các táo. Cụ thể như sau: sẽ có \(1\) con đường phân nhánh vô hạn, với nút đầu luôn có giá trị là \(1\). Các táo sẽ phải di chuyển tối đa \(n\) bước, bước đầu tiên sẽ đi vào nút gốc, các bước sau có thể chọn \(L\) hoặc \(R\). Với \(L\): nút tiếp theo sẽ có giá trị nhân đôi lên so với nút trước đó, với \(R\): nút tiếp đó sẽ có giá trị nhân đôi lên cộng \(1\) so với nút trước đó. VD ta có đồ thị như sau:

                                                                            1
                                                                           / \     
                                                                          /   \     
                                                                         /     \     
                                                                    2(1.2=2)  3(1.2+1=3)

Số điểm bạn đạt được sẽ là tổng tất cả các nút bạn đã đứng sau \(n\) bước. Ngọc hoàng đang thắc mắc rằng tổng số điểm với tất cả các khả năng có thể xảy ra là bao nhiêu, do quá mệt mỏi sau \(1\) năm điều hành các táo nên ngọc hoàng quyết định nhờ táo mạng, nhưng chợt nhớ các bạn trên LQDOJ, với lại lười search mạng quá và còn phải tập luyện nên táo mạng xin nhờ các bạn hãy giải quyết thắc mắc của ngọc hoàng giúp nhé!

Input

  • Duy nhất 1 số \(n(n\le 10^6)\)

Output

  • Duy nhất 1 số là kết quả của bài toán sau khi mod \(10^9+7\)

Example

Test 1

Input
3
Output
44
Note

Ta có hình vẽ:

                                                                    1
                                                                / \     
                                                                /   \     
                                                                /     \  
                                                                /       \   
                                                            2         3
                                                            / \       / \
                                                            /   \     /   \
                                                            /     \   /     \
                                                        4       5 6       7

Ở đây các khả năng có thể xảy ra gồm: \(1(1), 3(1+2), 4(1+3), 7(1+2+4), 8(1+2+5), 10(1+3+6), 11(1+3+7).\) Tổng là \(44\)


Bình luận

Không có bình luận nào.