0440 - Editorial

Tried variations of 0386, either MLE or TLE.
Then tried to skip certain recursive calls by checking if current k is smaller then k and value is bigger than n.
But couldnt figure out the math, it was fine for prefix 1 ish but at a certain point the math failed.
It might be possible to solve that way but I've dumped too much time into this.