j01968. 合法码字 未做

某编码器规定：一个正整数的二进制表示（不含前导零）中不允许出现相邻的两个 1，这样的数称为「合法码字」。给出 $N$，问 1$\dots$$N$ 中有多少个合法码字。

一行一个整数 $N$。

一行一个整数，合法码字个数。

• 30% 1$\le$$N$$\le$$1\times 10^6$（逐个检查 ($x$&($x$>>1))==0 可过）。
• 60% 1$\le$$N$$\le$$1\times 10^{12}$。
• 100% 1$\le$$N$$\le$$1\times 10^{18}$（须二进制数位 DP）。