Гра S-Грюнді

Нехай $\text{S}$ — деяка множина цілих невід'ємних чисел. Побудуємо на ній послідовність G_S(n) (n > 0) за наступною формулою:

Де $\text{mex}A$ — найменше ціле невід'ємне число, яке не належить множині $A$, а $a\text{xor}b$ — результат побітового додавання чисел $a$ та $b$ по модулю $2$.

Будемо називати множину $S$ доброю, якщо G_S(n+4)=G_S(n) при n>4, а значення G_S(n) при n=1,2,3,4,5,6,7,8 рівні 0,0,0,1,0,2,1,3 відповідно.

Задано n\geq0. Потрібно знайти кількість добрих множин, елементи яких не перевищують $n$, по модулю 10^9+7.