# Is there an efficient way to calculate last digits of this sum?

Is there a more efficient way to find the last digits of the following sum for any n?

$$1 + n + n(n-1) + n(n-1)(n-2) + ... + \frac{n}{2!} + n!$$

The method I currently use to find the last $$d$$ digits of the sum is as follows:

Let M be $$n \mod 10^d$$, or $$n \mod 10^d +10^d$$ if $$n \mod 10^d < 5\times d$$ since an additional step would affect the result if the latter is true. Evaluate 1 + M + M(M-1), then add M(M-1)(M-2), and continue until the number of desired digits stabilize.

This can be done quickly for a small number of digits, but for, say, 20 digits, it would be very time-consuming. Is there a way to program this in Mathematica? As far as I'm sure, this would require a loop that references the number of iterations that have been looped, which the Nest function doesn't do.

There is some undocumented functionality in Mathematica that allows you to work with a factored representation of integers, encapsulated as the object InternalFactoredNumber[]. This has associated operators such as InternalFactoredNumberTimes[] and InternalFactoredNumberPlus[] that can be used on it, as well as the conversion functions InternalToFactoredNumber[], InternalFromFactoredNumber[], and, most importantly for our purposes, InternalFromFactoredNumberMod[].

Applied to this problem, we can use these operations along with Fold[]/FoldList[]:

With[{n = 20, m = 1*^5},
InternalFromFactoredNumberMod[Fold[InternalFactoredNumberPlus, 1,
FoldList[InternalFactoredNumberTimes,
InternalToFactoredNumber /@
Range[n, 2, -1]]], m]]
40001


Compare this with

With[{n = 20, m = 1*^5},
Mod[Sum[FactorialPower[n, k], {k, 0, n - 1}], m]]
40001