这道题虽然有公式（看题解），但是一般做法太慢了（1.2s一个点了解一下）。

那么，我们如何AC呢？（我TLE3次QAQ）

首先，快读快写是必须要有的。

其次inline、register之类的优化关键字能开就开

再其次，cmath里的pow非常慢！记得手写一个位运算版的。

最后，也是最重要的一点，卡常+O2（虽然我都没开）