In english tutorial of https://codeforces.net/contest/460/problem/A, it is given that answer can be calculated using formula
/predownloaded/10/b1/10b1e92c780fc1e3547bba68ddaa8eb3e91c6576.png, but I am not able to understand how we reached at this formula. Please help me in this.
Here is my accepted submission , but my solution will exceed time limit if value of n is very large. Fortunately in this question input size limit is very small hence my solution works.