public class Euler171 {
    public static void main(String[] args) {
        int length = 20;
        int MOD = 1000000000;
        int maxSq = length * 81;
        long[][] count = new long[length + 1][maxSq + 1];
        long[][] sumV = new long[length + 1][maxSq + 1];
        long[] pow10 = new long[length + 1];
        pow10[0] = 1;
        for (int i = 1; i <= length; i++)
            pow10[i] = pow10[i - 1] * 10 % MOD;
        count[0][0] = 1;
        for (int ln = 1; ln <= length; ln++)
            for (int d = 0; d <= 9; d++) {
                int sq = d * d;
                for (int s = sq; s <= maxSq; s++) {
                    long cp = count[ln - 1][s - sq], sp = sumV[ln - 1][s - sq];
                    if (cp == 0 && sp == 0)
                        continue;
                    count[ln][s] = (count[ln][s] + cp) % MOD;
                    long add = (sp + pow10[ln - 1] * d % MOD * cp) % MOD;
                    sumV[ln][s] = (sumV[ln][s] + add) % MOD;
                }
            }
        long ans = 0;
        for (int r = 1; r * r <= maxSq; r++)
            ans = (ans + sumV[length][r * r]) % MOD;
        System.out.println(ans);
    }
}