小蓝面前排列着 盏灯，每盏灯起初要么是亮的，要么是灭的。因此，一共有 种不同的初始状态。
对于某种初始状态，小蓝会进行 次独立的观察，每次观察均直接从该初始状态出发（各次观察之间互不影响）：
- 第 次观察：不改变任何灯的状态，记录此时整排灯中亮灯的数量。
- 第 次观察（）：在初始状态的基础上，先将前 盏灯的状态进行反转（亮变灭、灭变亮），然后记录此时整排灯中亮灯的数量。
记这 次观察得到的亮灯数量依次为 。如果在序列 中，不同元素的个数恰好为 ，则称这个初始状态是美好的。
现在，请你帮助小蓝计算，一共有多少种美好的初始状态。由于答案可能很大，你只需要给出答案对 取模后的结果即可。
