Now I’ve enough karma to start a new thread, so thank you people for upvotes.
I read the CHN08 - Editorial, and after that I came up this solution which works very fine. But I’m not able to understand why I have to add modular(10^7+1) to
temp<0. I’m talking about this line.