dp全然わからん

https://atcoder.jp/contests/typical90/tasks/typical90_e

https://drken1215.hatenablog.com/entry/2021/10/08/231200

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

const mod int = 1000000007
const log int = 62

func main() {

	scanner := bufio.NewScanner(os.Stdin)

	scanner.Scan()
	s := strings.Split(scanner.Text(), " ")

	n, _ := strconv.Atoi(s[0])
	b, _ := strconv.Atoi(s[1])
	k, _ := strconv.Atoi(s[2])

	cs := make([]int, k)
	scanner.Scan()
	for i, c := range strings.Split(scanner.Text(), " ") {
		cs[i], _ = strconv.Atoi(c)
	}

	mul := func(dpi, dpj []int, tj int) []int {

		res := make([]int, b)
		for p := 0; p < b; p++ {
			for q := 0; q < b; q++ {
				res[(p*tj+q)%b] += dpi[p] * dpj[q]
				res[(p*tj+q)%b] %= mod
			}
		}

		return res
	}

	ten := make([]int, log)
	for i := 0; i < len(ten); i++ {
		ten[i] = 10
	}

	for i := 1; i < len(ten); i++ {
		ten[i] = (ten[i-1] * ten[i-1]) % b
	}

	doubling := make([][]int, log)
	for i := 0; i < len(doubling); i++ {
		doubling[i] = make([]int, b)
	}

	for i := 0; i < k; i++ {
		doubling[0][cs[i]%b] += 1
	}

	for i := 1; i < log; i++ {
		doubling[i] = mul(doubling[i-1], doubling[i-1], ten[i-1])
	}

	res := make([]int, b)
	res[0] = 1
	for i := 0; i < log; i++ {
		if n&(1<<i) != 0 {
			res = mul(res, doubling[i], ten[i])
		}
	}

	fmt.Print(res[0])
}