Note: Đây chỉ là 1 bài tập nhỏ.

Sau khi thất bại trước Tây Ban Nha bởi bàn thắng của Ferran Torres ở phút 106 của trận chung kết FIFA World Cup 2026, hành trình của Lionel Messi tại ngày hội bóng đá lớn nhất hành tinh có lẽ đã chính thức khép lại. Không có cái kết cổ tích với chiếc cúp vàng thứ hai, không có nụ cười rạng rỡ như đêm Doha năm 2022, chỉ còn lại hình ảnh người đội trưởng 39 tuổi lặng lẽ cúi đầu giữa biển người đang vỡ òa trong niềm vui của đối thủ. Nhưng kỳ lạ thay, chẳng ai nhìn Messi bằng ánh mắt của một kẻ thất bại. Bởi hơn hai mươi năm cống hiến, anh đã viết nên một câu chuyện đẹp đến mức một thất bại cuối cùng cũng không thể xóa nhòa.

Có lẽ sẽ chẳng ai quên được cậu bé nhỏ con đến từ Rosario năm nào. Một cậu bé phải rời quê hương khi mới mười ba tuổi để sang Tây Ban Nha chữa bệnh, mang trong mình giấc mơ một ngày nào đó sẽ được khoác lên chiếc áo sọc xanh trắng của Argentina. Năm 2005, giấc mơ ấy thành hiện thực, nhưng cũng thật trớ trêu khi trận ra mắt đội tuyển quốc gia của Messi chỉ kéo dài chưa đầy một phút. Một chiếc thẻ đỏ, một cái cúi đầu lặng lẽ rời sân. Không ai ngờ rằng cậu bé ấy sau này sẽ trở thành cầu thủ ra sân nhiều nhất, ghi nhiều bàn thắng nhất và là biểu tượng vĩ đại nhất trong lịch sử bóng đá Argentina.

World Cup 2006 là nơi cả thế giới bắt đầu biết đến cái tên Lionel Messi. World Cup 2010 là nơi anh phải lặng lẽ rời cuộc chơi trong sự thất vọng. World Cup 2014 lại là nơi cả thế giới khóc cùng anh. Chỉ còn một bước nữa thôi, chỉ còn một trận đấu nữa thôi, chiếc cúp vàng đã ở ngay trước mắt. Nhưng định mệnh lại quá nghiệt ngã. Phút 113 của trận chung kết, Mario Götze ghi bàn. Messi đứng bất động. Sau tiếng còi mãn cuộc, anh lặng lẽ bước ngang qua chiếc cúp vàng, đôi mắt nhìn về nó đầy tiếc nuối rồi cúi đầu bước tiếp. Bức ảnh ấy đến tận hôm nay vẫn khiến hàng triệu người yêu bóng đá nghẹn ngào. Người ta thường nói thời gian sẽ chữa lành mọi vết thương, nhưng có những nỗi đau chẳng bao giờ biến mất.

Rồi Copa América 2015... rồi Copa América Centenario 2016... Hai trận chung kết, hai lần thất bại trên chấm luân lưu. Trong trận đấu năm 2016, Messi đá hỏng quả penalty của mình. Khi bóng bay vọt lên bầu trời New Jersey, dường như cả thế giới cũng lặng đi. Sau trận đấu, anh bật khóc. Lần đầu tiên, người đội trưởng mạnh mẽ ấy không thể giấu nổi sự tuyệt vọng. Trước hàng triệu người hâm mộ, Messi nghẹn ngào nói rằng đội tuyển quốc gia không còn dành cho mình nữa. Anh tuyên bố chia tay Argentina.

Đó là khoảnh khắc đau lòng nhất trong sự nghiệp của Lionel Messi.

Suốt nhiều năm, anh đã gánh trên vai áp lực của cả một dân tộc. Người ta không nhìn anh như một con người bình thường. Người ta bắt anh phải trở thành Maradona thứ hai. Mỗi lần Argentina thất bại, mọi ánh mắt đều hướng về Messi. Có người chỉ trích anh không đủ bản lĩnh. Có người nói anh chỉ biết tỏa sáng trong màu áo Barcelona. Có người còn đốt chiếc áo số 10 của anh vì thất vọng. Chưa từng có một thiên tài nào lại phải mang trên vai nhiều gánh nặng đến như vậy.

Nhưng rồi, chính tình yêu dành cho quê hương đã kéo anh trở lại.

Messi không quay về để chứng minh mình giỏi hơn ai. Anh cũng không quay về để đáp trả những lời chỉ trích. Anh quay về vì trái tim mình vẫn thuộc về Argentina. Bởi sâu thẳm trong con người ấy vẫn còn một giấc mơ chưa hoàn thành.

Và rồi bóng đá đã mỉm cười với người chưa bao giờ từ bỏ.

Năm 2021, Argentina vô địch Copa América sau 28 năm chờ đợi. Khi tiếng còi mãn cuộc vang lên trên sân Maracanã, Messi quỳ xuống mặt cỏ, hai tay ôm lấy khuôn mặt đã ướt đẫm nước mắt. Đó không chỉ là nước mắt của niềm vui. Đó là nước mắt của sáu năm thất bại liên tiếp, của những lời chỉ trích, của những đêm không ngủ, của biết bao lần tưởng như muốn buông xuôi.

Rồi Qatar 2022 đến.

Sau thất bại gây sốc trước Saudi Arabia, cả thế giới lại nghi ngờ anh. Nhưng Messi chỉ mỉm cười. Anh lặng lẽ dẫn dắt Argentina đi qua từng trận đấu. Mexico, Ba Lan, Australia, Hà Lan, Croatia rồi Pháp... ở đâu cũng có dấu ấn của số 10. Và khi Gonzalo Montiel thực hiện thành công quả penalty quyết định, Messi khuỵu xuống. Anh ôm chiếc cúp vàng như ôm cả giấc mơ đã theo đuổi gần hai mươi năm. Đó không chỉ là chiếc cúp của riêng Messi. Đó là phần thưởng dành cho một con người chưa từng đầu hàng số phận.

Nếu ngày hôm ấy, sau Copa América 2016, Messi thực sự rời đội tuyển quốc gia thì sao?

Sẽ không có Maracanã 2021.

Sẽ không có Lusail 2022.

Sẽ không có những giọt nước mắt hạnh phúc của hàng triệu người Argentina.

Chỉ một quyết định ở lại... đã thay đổi cả lịch sử bóng đá.

Rồi thời gian vẫn trôi. Mái tóc Messi đã dần điểm bạc. Những bước chạy không còn nhanh như tuổi đôi mươi. Nhưng trái tim của anh thì chưa bao giờ già đi.

World Cup 2026, ở tuổi 39, khi nhiều huyền thoại đã giải nghệ từ rất lâu, Messi vẫn là linh hồn của Argentina. Anh ghi tám bàn thắng, kiến tạo bốn lần, đưa đội tuyển vào trận chung kết World Cup lần thứ hai liên tiếp. Anh chiến đấu như thể đó là trận đấu cuối cùng của cuộc đời mình.

Và đúng là như vậy.

Phút 106...

Ferran Torres ghi bàn.

Tiếng còi mãn cuộc vang lên.

Messi cúi đầu.

Có lẽ chính anh cũng hiểu, hành trình World Cup của mình đã khép lại.

Nhưng lần này,anh đã chiến thắng những lời chế giễu, chiến thắng những thất bại, chiến thắng chính bản thân mình. Giờ đây lại rời World Cup trong tiếng vỗ tay của cả thế giới.

Có người sẽ nhớ Messi vì những bàn thắng. Có người sẽ nhớ anh vì những pha đi bóng như đang nhảy múa với trái bóng. Nhưng với tôi, điều vĩ đại nhất ở Lionel Messi chưa bao giờ là tài năng. Điều vĩ đại nhất là sau mỗi lần gục ngã, anh luôn đứng dậy. Sau mỗi lần nước mắt rơi, anh lại mỉm cười bước tiếp.

Bởi vậy, khi Messi rời sân lần cuối trong màu áo Argentina ở một kỳ World Cup, có lẽ một kỷ nguyên cũng khép lại. Thế giới sẽ mất đi một thiên tài, nhưng bóng đá sẽ mãi mãi giữ lại câu chuyện về một con người đã dành cả cuộc đời để yêu quê hương, để theo đuổi giấc mơ và để chứng minh rằng: huyền thoại không phải là người chưa từng thất bại, mà là người chưa bao giờ đầu hàng trước thất bại.

Nhiệm vụ

• Cho số nguyên dương \(N\). Hãy đếm số lượng dãy số có độ dài đúng bằng \(N\), các phần tử thuộc tập \(\{1, 2, ..., N\}\) sao cho không có hai phần tử liên tiếp nào cùng tính chẵn lẻ. In ra kết quả theo modulo \(10^9 + 7\).

Input

• Nhập vào 1 số nguyên dương \(N\) (\(1 \le N \le 10^9\))

Output

• Một số nguyên duy nhất là số lượng dãy số tìm được theo modulo \(10^9 + 7\).

Example

3

6