\(L\) оң бүтін саны екілік жүйеде берілген. Келесі шарттарды қанағаттандыратын теріс емес бүтін сандар жұптары \((a, b)\) қанша?

• \(a + b \le L\)

• \(a + b = a \oplus b\) (мұндағы \(\oplus\) — биттік алып тастау НЕМЕСЕ)

Жауап өте үлкен болуы мүмкін болғандықтан, оны \(10^9 + 7\) модулі бойынша шығарыңыз.

Енгізу

Жалғыз жолда \(L\) саны екілік санау жүйесінде, жетекші нөлдерсіз жазылған (\(1 \le |L| \le 10^6\), яғни \(1 \le L < 2^{10^6}\)).

Шығару

Шарттарды қанағаттандыратын \((a, b)\) жұптарының санын \(10^9 + 7\) модулі бойынша шығарыңыз.

Бағалау жүйесі

Мысалдар

Енгізу 1

10

Жауап 1

5

Енгізу 2

11

Жауап 2

9

Ескертпелер

Бірінші мысалда \(L = 10_2 = 2\). Сәйкес жұптар: \((0,0)\), \((0,1)\), \((1,0)\), \((0,2)\), \((2,0)\). Барлығы \(5\).

Екінші мысалда \(L = 11_2 = 3\). Алдыңғы \(5\) жұпқа \((1,2)\), \((2,1)\), \((0,3)\), \((3,0)\) қосылады. Барлығы \(9\).