matrix

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 BigInteger[] nums;
  static {
    nums = new BigInteger[11];
    for (int i = 0; i <= 10; i++)
      nums[i] = new BigInteger(String.valueOf(i));
  }

  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);
    }

    BigInteger[][][] trans = new BigInteger[res.length][98][98];
    for (int r = 0; r < res.length; r++) {
      for (BigInteger[] x : trans[r]) Arrays.fill(x, BigInteger.ZERO);
      for (int i = 0; i < 49; i++) {
        int k = i/7, m = i%7;
        for (int j = 0; j <= 9; j++) {
          int nk = (k+res[bf]*j)%7, nm = (m+res[ff]*j)%7, nc = nk*7+nm;
          trans[r][i][nc] = trans[r][i][nc].add(BigInteger.TEN);
          trans[r][i+49][nc] = trans[r][i+49][nc].add(nums[j]);
          trans[r][i+49][nc+49] = trans[r][i+49][nc+49].add(BigInteger.ONE);
        }
      }
      bf++; if (bf >= res.length) bf -= res.length;
      ff--; if (ff < 0) ff += res.length;
    }
    BigInteger[][] x = new BigInteger[98][98];
    for (int i = 0; i < 98; i++) {
      Arrays.fill(x[i], BigInteger.ZERO);
      x[i][i] = BigInteger.ONE;
    }
    for (int r = 0; r < res.length; r++) x = mat_mult(x, trans[r]);
    x = mat_exp(x, lim/res.length);
    for (int r = 0; r < lim % res.length; r++) x = mat_mult(x, trans[r]);
    return x[49][0];
  }

  public static BigInteger[][] mat_mult(BigInteger[][] a, BigInteger[][] b) {
    int n = a.length;
    BigInteger[][] c = new BigInteger[n][n];
    for (BigInteger[] x : c) Arrays.fill(x, BigInteger.ZERO);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++)
      c[i][j] = c[i][j].add(a[i][k].multiply(b[k][j]));
    return c;
  }

  private static BigInteger[][] mat_exp(BigInteger[][] A, int e) {
    if (e == 1)
      return A;
    else if (e % 2 == 0) {
      BigInteger[][] A1 = mat_exp(A, e / 2);
      return mat_mult(A1, A1);
    } else
      return mat_mult(A, mat_exp(A, e - 1));
  }

}