Some basic permutations

Let $f(n)$ equal the average over all permutations of the digits $1$ to $n$ (inclusive) interpreted in base $n+1$ . For example, for $f(3)$ we have

$(123)_4 = (27)_{10}$ $(132)_4 = (30)_{10}$ $(213)_4 = (39)_{10}$ $(231)_4 = (45)_{10}$ $(312)_4 = (54)_{10}$ $(321)_4 = (57)_{10}$

for an average value of $42$ (in base 10).

Find $f(10^6)$ mod $1000037$ .