revdiv7

import java.math.BigInteger;
import java.util.Arrays;

public class div7 {
  // main idea taken from here: https://www.math.hmc.edu/funfacts/ffiles/10005.5.shtml
  public static int MAXD = 10000;
  public static int[] res = {1,3,2,6,4,5}; // 10^i modulo 7, repeating

  public static void main (String[] args) {
    long start = System.currentTimeMillis();
    BigInteger sum = count(MAXD);
    int x = 0;
    for (char c : sum.toString().toCharArray()) x += c-'0';
    System.out.println("Sum digits: " + x);
    if (sum.toString().length() < 1000) System.out.println("Sum: " + sum);
    System.out.println("Time: " + (System.currentTimeMillis()-start) + "ms");
  }

  public static BigInteger count(int lim) {
    int bf = 0, ff = (lim - 1) % res.length;

    BigInteger[][] dp = new BigInteger[2][49];
    BigInteger[][] count = new BigInteger[2][49];
    for (int i = 0; i < 2; i++) {
      Arrays.fill(dp[i], BigInteger.ZERO);
      Arrays.fill(count[i], BigInteger.ZERO);
    }

    int cur = 0, next = 1;
    count[cur][0] = BigInteger.ONE;

    BigInteger ans = BigInteger.ZERO;
    for (int i = 0; i < lim; i++) {
      if (i % 1000 == 0) System.out.println(i+" "+ans.toString().length());

      Arrays.fill(dp[next], BigInteger.ZERO);
      Arrays.fill(count[next], BigInteger.ZERO);

      for (int cc = 0; cc < 49; cc++) {
        int k = cc/7, m = cc%7;
        BigInteger x = dp[cur][cc].multiply(BigInteger.TEN);
        for (int j = 0; j <= 9; j++) {
          int nk = (k+res[bf]*j)%7, nm = (m+res[ff]*j)%7, nc = nk*7+nm;
          dp[next][nc] = dp[next][nc].add(x);
          count[next][nc] = count[next][nc].add(count[cur][cc]);
          x = x.add(count[cur][cc]);
        }
      }
      cur ^= 1; next ^= 1;
      bf++; if (bf >= res.length) bf -= res.length;
      ff--; if (ff < 0) ff += res.length;
    }
    return dp[cur][0];
  }
}