请勿二分 log 的真数。已知 log 的增长性非常大，所以二分真数的时候，到二分后期就被劣化成 $k$ 分，且 $k$ 增长速度极快。

所以 $l \to 0,r\to \log 10^9$ 即可。

以及，精度可以多开一点，dp 常数小，最好预处理一下跳 fail，我是 $10^{-10}$，跑了 500ms 左右。