Company: Media net
Difficulty: medium
Space Race 2025 The year is 2025. The space race is in full motion. Elon Musk and Jeff Bezos have already launched their rockets into space. Bill Gates on the other hand, is struggling to even get started. However, his good friend Elon, offers him his secret rocket fuel formula if Gates is able to solve a particular problem. There are A planets. Jeff\'s space company is not very good so he can only jump from the ith planet to the (i+1)th planet and (i+2)th planet. Let XJ be the array of integers representing the number of ways to get to the ith planet if Jeff starts from the 1st planet. XJ[0] would be 1. Since the values can be very large, consider them all modulo 1e9+7. Elon\'s space company is quite advanced compared to Jeff\'s. So from the ith planet, Elon\'s rocket can jump to all planets such that: For every set bit in XJ[i]\'s binary representation, Elon\'s rocket when at the ith planet can jump ahead by values in the range [2 k , 2 k+1 ) Let XJ[i] be 5. It\'s binary representati