两侧街道的房屋放置方案数
两侧街道的房屋放置方案数
题目描述
一条街道上有 个地块，街道两侧各有 个地块，每侧的地块按从 到 编号。每个地块上可以选择放置一所房子或不放置。
限制条件：在同一侧街道上，不能有两所房子位于相邻的地块上（即同一侧不能有两个连续编号的地块同时建房）。
两侧街道相互独立——在一侧第 个地块建房，不影响另一侧第 个地块是否建房。
请你计算所有合法的房屋放置方案总数。由于答案可能很大，请将结果对 取模后返回。
输入格式
一行，一个正整数 （），表示街道每一侧的地块数量。
输出格式
一个整数，表示合法的房屋放置方式数目对 取模后的结果。
示例
示例 1
输入：
1
输出：
4
解释：
- 两侧都不建房；
- 仅左侧建房；
- 仅右侧建房；
- 两侧都建房（各在第 1 块地）。
共 4 种方案。
示例 2
输入：
2
输出：
9
解释：
每侧有 3 种合法建房方式（空、只建第1块、只建第2块），两侧独立，总方案数为 。