AT_wtf19_b.Multiple of Nine

请计算满足以下条件的字符串 $S$ 的个数，并将结果对 $10^9+7$ 取模。

• $S$ 的长度恰好为 $N$。
• $S$ 仅由数字（0 到 9）组成。
• 给定 $Q$ 个区间。对于每个 $i\ (1 \leq i \leq Q)$，要求 $S[l_i \ldots r_i]$（即 $S$ 的第 $l_i$ 个字符到第 $r_i$ 个字符，包含两端）所表示的整数必须是 $9$ 的倍数。

这里，字符串 $S$ 及其子串可以以 $0$ 开头。例如，002019 表示整数 $2019$。

输入按以下格式从标准输入读入。

$N$ $Q$ $l_1$ $r_1$ $:$ $l_Q$ $r_Q$

输出满足条件的字符串个数，对 $10^9+7$ 取模。

限制条件

• $1 \leq N \leq 10^9$
• $1 \leq Q \leq 15$
• $1 \leq l_i \leq r_i \leq N$

样例解释 1

例如，$S = $9072 满足条件。因为 $S[1 \ldots 2] = $90 和 $S[2 \ldots 4] = $072 都是 $9$ 的倍数。

由 ChatGPT 4.1 翻译