AT_wtf19_b Multiple of Nine

[problemUrl]: https://atcoder.jp/contests/wtf19/tasks/wtf19_b 以下の条件を満たす文字列 $ 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 $ 文字目 (先頭を $ 1 $ 文字目とする) から $ r_i $ 文字目まで (両端含む) の部分文字列) が表す整数は $ 9 $ の倍数でなければならない。 ここで、文字列 $ S $ やその部分文字列が $ 0 $ から始まっても構いません。 例えば、`002019` は整数 $ 2019 $ を表します。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 10^9 $ - $ 1\ \leq\ Q\ \leq\ 15 $ - $ 1\ \leq\ l_i\ \leq\ r_i\ \leq\ N $ ### Sample Explanation 1 例えば、$ S\ = $`9072` は条件を満たします。なぜなら、$ S[1\ \ldots\ 2]\ = $`90` と $ S[2\ \ldots\ 4]\ = $`072` がいずれも $ 9 $ の倍数であるためです。