I’m a rookie competitive coder. Although I expected to solve this problem, yet I was stumped by only getting partially correct response (rest of the cases went TLE) despite thinking of alternate approaches. I’m thus quite curious as to what the actual answer is. Since I’m not sure when the solution for it will be made available, I thought if asking those who successfully solved this problem - what did you guys use?
My approach - I created a recurrence relation for the nth term: g(n) = n + (n + 1) * g(n-1) with initial conditions: g(0) = 0, g(1) = 1.
There’s no closed form solution to it except for the following:
g(n) = (n+1)! - 1
I thus calculated the above factorial mod (10^9 + 7).
I’m not sure what the fastest way is to compute the above (except for wilson’s theorem which is, I believe, about ((p-N)logN) or effectively NlogN (didn’t try it - Is that the case? ))