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 翻译