Project Euler 335 - Gathering the beans

Official link: https://projecteuler.net/problem=335

Thought Process

This is my 250th problem solved, and my LEAST favourite problem solved so far, as I found the correct sequence completely by being lucky.

A simple replication of the game gets me the first 34 values of M(n), they are:
[1, 2, 5, 12, 15, 34, 40, 46, 53, 114, 126, 138, 152, 164, 178, 192, 207, 430, 454, 478, 506, 530, 558, 586, 616, 640, 668, 696, 726, 754, 784, 814, 845, 1722, 1770]

I find some peculiar pattern between each value:

*2, *2 + 1, *2 + 2, +3, *2 + 4, +6, +6, +7, *2 + 8, +12, +12, +14, +12, +14, +14, +15, *2 + 16, +24, +24, +28, +24, +28, +28, +30, +24, +28, +28, +30, +28, +30, +30, +31, *2 + 32

Notice that red values correspond the exact values we are interested in, there is clearly a pattern with powers of 2.

I find the first 10 values of M(2^k + 1), they are:
[2, 5, 15, 53, 207, 845, 3495, 14453, 59487, 243485]

Now from these I subtract 2^(k + 1), I get:
[0, 1, 7, 37, 175, 781, 3367, 14197, 58975, 242461] which I luckily found on OEIS: https://oeis.org/A005061 which is 4^k - 3^k

We then have the following, UNPROVEN, equations:

Interactive Code

Input an integer (yourinput)

Code will output ΣM(2^k + 1) mod 7^9, k = 0 to yourinput