### 问题描述 在远古的魔法大陆 "Eldoria" 中，魔法师们会通过召唤符咒来召唤魔法生物。这些召唤符咒可以召唤三种神秘的远古生物组成：召唤龙、召唤仙子、召唤元素生物。最关键的是按照一定的顺序召唤这三种神秘的远古生物可以召唤出一只强大的魔法生物。 要召唤出一只强大的魔法生物，魔法师必须遵循以下规则： 1. 魔法师的召唤符咒中，召唤龙不能出现超过一次。 2. 魔法师的召唤符咒中，召唤仙子不能连续出现 $3$ 次或以上。 给你一个整数 $n$，代表魔法师想要创造的召唤符咒的召唤次数。请计算在连续 $n$ 次召唤中，可能成功召唤强大的魔法生物的符咒组合数量。由于可能的组合数量可能非常大，返回结果需对 $10^9 + 1$ 取余。 ### 输入格式 一个整数 $n$ 。 ### 输出格式 一个整数，表示长度为 $n$ 的召唤符咒中，可能成功召唤强大的魔法生物的组合数量对 $10^9 + 1$ 取余的结果。 ### 样例输入 ```text 2 ``` ### 样例输出 ```text 8 ``` ### 说明 有 $8$ 种召唤次数为 $2$ 的召唤符咒将被视为成功： 假设，召唤龙为符咒 $A$，召唤仙子为符咒 $B$,召唤元素生物为符咒 $C$。 那么分别是：$AB$，$AC$， $BA$，$BB$，$BC$，$CC$，$CB$，$CA$。 只有 $AA$（连续召唤两次龙）不会被视为成功，因为召唤龙的符咒出现了 2 次。 ### 评测数据规模 对于 $50$% 的评测数据，$1\leq n \leq 10^3$。 对于 $100$% 的评测数据，$1 \leq n \leq 10^5$。