S-Gründi Oyunu

Qoy S - bəzi tam qeyri-mənfi ədədlər çoxluğu olsun. Bu çoxluq üzərində G_S(n) (n > 0) ardıcıllığını aşağıdakı düsturla quraq:

burada mex A - A çoxluğuna daxil olmayan ən kiçik tam qeyri-mənfi ədəddir, a xor b isə a və b ədədlərinin bitwise əlavə etmə əməliyyatının 2 modulu üzrə nəticəsidir.

Çoxluğu S yaxşı adlandıracağıq, əgər G_S(n+4)=G_S(n) n > 4 üçün və G_S(n) dəyərləri n=1,2,3,4,5,6,7,8 üçün müvafiq olaraq 0,0,0,1,0,2,1,3 bərabərdir.

Verilmişdir n ≥ 0. Elementləri n-dən böyük olmayan yaxşı çoxluqların sayını 10^9+7 modulu üzrə tapmaq lazımdır.

Giriş verilənləri

Giriş faylının yeganə sətrində tam qeyri-mənfi n ≤ 10^18 ədədi verilir.

Çıxış verilənləri

Çıxış faylının yeganə sətrində məsələnin cavabını çıxarın.

Nümunələr