a331. TOI 2023/10 潛力組：物聯網裝置

題目描述

一個物聯網裝置會依序送出位元訊號，1 表示正常，0 表示不安定。主控系統只要連續收到四個 0，就立即將裝置關機。

現在裝置自開機起已送出 N 個位元，且尚未關機。請計算這 N 個位元形成的訊號序列共有多少種可能，並將答案對 10^9+7 取餘數。

輸入格式

輸入一個整數 N，1 ≤ N ≤ 2^60。

原題分組限制：10 分：N ≤ 20。30 分：N ≤ 2^20。60 分：無額外限制。

輸出格式

輸出一個整數，表示可能的訊號序列數除以 10^9+7 的餘數。

範例 1

輸入：

2

輸出：

4

範例 2

輸入：

5

輸出：

29

範例 3

輸入：

106

輸出：

644528034

範例 4

輸入：

21474836

輸出：

352283007

來源

TOI 2023 年 10 月歷屆題〈物聯網裝置〉，依官方 PDF 重新整理。

官方原題：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202310/IOT.pdf

標籤：TOI 歷屆