我试图用组合和计数子集来解决相当复杂的问题。首先，我们给定集合A = {1,2,3，… N}，其中N <= 10
^（18）。现在，我们要计算其表示中没有连续数字的子集。

例

假设N = 3，而A = {1,2,3}。总共有2 ^
3个子集，但我们不想计算子集（1,2），（2,3）和（1,2,3）。因此，对于这个问题，我们总共要回答5，因为我们只想计算剩余的5个子集。这些子集是（空子集），（1），（2），（3），（1,3）。我们也想以10
^ 9 + 7为模来打印结果。

到目前为止我做了什么

我当时以为应该使用带有两个状态的动态规划来解决这个问题（我们是否采用第i个元素），但是后来我看到N可以上升到10 ^
18，所以我以为应该解决这个问题使用数学公式。您能给我一些提示，我应该从哪里开始获取公式。

提前致谢。