思路

• 核心是数位 DP，带“非严格单调约束”和“数位和按模取值”的统计。

• 为了应对多达 $Q=500$ 次不同 $d$ 的查询，直接把 $d$ 放入 DP 状态会在 Python 中偏慢。优化思路：把“模运算”延后，用“数位和分布向量”预处理，然后对每个 $d$ 再按模聚合。

• 预处理定义：

  • 设 $ways[L][min][s]$ 表示长度为 $L$ 的非降序数字序列（允许前导零，但当前位必须 $\ge min$），其数位和为 $s$ 的方案数。
  • 转移：

题目内容

我们称一个正整数为"升数"，当且仅当其十进制表示的各位数字从高位到低位单调不降(例如 $1123、5$ )。

给定一个正整数 $m$ 和查询次数 $Q$ 。每个查询给出一个正整数 $d$ 。

请统计所有不超过 $m$ 的升数中，数位之和能被 $d$ 整除的升数个数。

【名词解释】

• 升数：升数 是其十进制表示中，除首位外每个数字不小于其左侧相邻数字的正整数。

输入描述

第一行输入两个整数 $m,Q(1≤m ≤ 10^{18},1≤Q≤ 500)$，分别表示上限和查询次数。

接下来 $Q$ 行，每行输入一个整数 $d(1 ≤d≤ 200)$ ，表示查询的模数。

输出描述

输出 $Q$ 行，第 $i$ 行输出一个整数，表示所有小于等于 $m$ 的升数中，数位和对 $d_i$ 取模为 $0$ 的个数。

样例1

输入

50 2
1
10

输出

39
4

说明

从 $1$ 到 $50$ 中，升数一共有 $39$ 个，其中数位和模 $10$ 等于 $0$ 的一共有 $4$ 个，分别是 $19,28,37,46$ 。

样例2

输入

100 3
3
4
7

输出

18
14
7