This question doesn't support checking answers.

749. Near Power Sums

A positive integer, $n$, is a near power sum if there exists a positive integer, $k$, such that the sum of the $k$th powers of the digits in its decimal representation is equal to either $n+1$ or $n-1$. For example 35 is a near power sum number because $3^2+5^2 = 34$.

Define $S(d)$ to be the sum of all near power sum numbers of $d$ digits or less. Then $S(2) = 110$ and $S(6) = 2562701$.

Find $S(16)$.