Хэрэв тухайн тоонд $d$ гэсэн цифр бүх тэгш байрлалууд дээр байх бөгөөд сондгой байрлалуудад байхгүй байвал уг тоог "$d$-шидэт" гэж нэрлэе.

Жишээлбэл $1727374$, $17$, $1$ гэсэн тоонууд нь "$7$-шидэт" тоонууд бөгөөд $77$, $7$, $123$, $34$, $71$ гэсэн тоонууд нь "$7$-шидэт" тоонууд биш юм. Өөрөөр хэлбэл $7$ бол "$0$-шидэт" тоо, $123$ бол "$2$-шидэт" тоо, $34$ бол "$4$-шидэт" тоо бөгөөд $71$ бол "$1$-шидэт" тоо юм.

Тэгвэл $[a, b]$ завсарт байх бөгөөд $m$ тоонд хуваагдах "$d$-шидэт" тоонуудын тоог олно уу. Хариулт нь маш том тоо гарч болох учраас хариултынхаа $(10^{9} + 7)$-д хуваасан үлдэгдлийг олно уу.

Оролт

Эхний мөрөнд өгөгдсөн нөхцлүүд болох бүхэл тоо $m, d$ өгөгдөнө. $(1 ≤ m ≤ 2000, 0 ≤ d ≤ 9)$

Хоёр дахь мөрөнд эерэг бүхэл $a$ тоо өгөгдөнө. Энэ тоо $0$-ээр эхлэхгүй.

Гурав дахь мөрөнд эерэг бүхэл $b$ тоо өгөгдөнө. Энэ тоо $0$-ээр эхлэхгүй.

$a ≤ b$ байх ба $a$ болон $b$ тоонууд нь ижил оронтой бөгөөд $2000$-аас хэтрэхгүй оронтой байна.

Гаралт

$[a, b]$ завсарт байх бөгөөд $m$ тоонд хуваагдах "$d$-шидэт" тоонуудын тоог $(10^{9} + 7)$-д хуваасан үлдэгдлийг хэвлэнэ үү.

Эхний жишээний хариунд тоологдох тоонууд нь $16$, $26$, $36$, $46$, $56$, $76$, $86$, $96$ болох юм.

Хоёр дахь жишээний хариунд тоологдох тоонууд нь $2$, $4$, $6$, $8$ болох юм.

Гурав дахь жишээний хариунд тоологдох тоонууд нь $1767$, $2717$, $5757$, $6707$, $8797$, $9747$ болох юм.