#cpsco2019s1d. [cpsco2019_s1_d]Dessert Planning

[cpsco2019_s1_d]Dessert Planning

你很喜欢吃点心,因此你制定了以下吃点心的规则:

  • 每天共吃 33 顿点心,早餐、午餐、晚餐。

  • 每顿吃的点心是曲奇、巧克力、蛋糕中的任一种。

  • 连续两顿(包括第 ii 天的晚餐与第 i+1i + 1 天的早餐)不能吃同样的点心。

  • 每天的早餐只能吃曲奇或巧克力。

假设你拥有足够的点心,问对于 NN 天共 3N3N 顿点心有几种满足上面规则的吃法组合?由于答案可能过大,请输出答案对 109+710^9 + 7 取模后的结果。