How to avoid WA 15 While calculating f[n] during another iteration of binary search, every time check if f[i] is out of [-2*10^9, 2*10^9]. If it is, immediately break calculation cycle, update binary search interval and start another its iteration.
I used formula and a C++ type long long, but still somehow managed to get WA 15. Even though i got around it by calculating in Zp (where p is a prime number bigger than 4 * 10^9), it still blows up my mind how it's possible to overflow long long without violating the statement. Such a tricky test, i'd like to see it.