Statement

Valerio is exploring sequences of integers by writing them on a blackboard. He starts a sequence with the numbers 1 and 2. Subsequently, he generates each new number according to one of the following rules: (1) The next number is the sum of the two preceding numbers. (2) The next number is twice the value of the preceding number. Now, Davide has seen the last number M written on the blackboard and is curious about all the possible sequences Valerio could have created. Help Davide figure out how many different sequences Valerio could have written!