title: Count the total number of subsets that don't have consecutive elements
body: <p>I'm trying to solve pretty complex problem with combinatorics and counting subsets. First of all let's say we have given set A = {1, 2, 3, ... N} where N &lt;= 10^(18). Now we want to count subsets that don't have consecutive numbers in their representation.</p>
  
  <p><strong>Example</strong></p>
  
  <p>Let's say N = 3, and A = {1,2,3}. There are 2^3 total subsets but we don't want to count the subsets (1,2), (2,3) and (1,2,3). So in total for this question we want to answer 5 because we want to count only the remaining 5 subsets. Those subsets are (Empty subset), (1), (2), (3), (1,3). Also we want to print the result modulo 10^9 + 7.</p>
  
  <p><strong>What I've done so far</strong></p>
  
  <p>I was thinking that this should be solved using dynamical programming with two states (are we taking the i-th element or not), but then I saw that N could go up to 10^18, so I was thinking that this should be solved using mathematical formula. Can you please give me some hints where should I start to get the formula.</p>
  
  <p>Thanks in advance.</p>