Rt

二分很一眼吧

然后把判定的那个除式乘开，然后直接DP就行。