Girl Numbers

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Love is a zigzag.

Tình yêu cũng giống như CF rating, có lúc lên lúc xuống. Một ngày buồn, Ami ngồi viết ra những con số vô thức. Khi nhìn lại, cậu nhận ra những con số vừa viết tạo thành một dãy số như nói hộ lòng mình. Những chữ số thay nhau tăng giảm, cứ tăng rồi lại giảm, cứ giảm rồi lại tăng. Cậu liền nghĩ ra một bài toán khá thú vị để đố đệ tử CaiWinDao.

Ami định nghĩa một số như cậu vừa viết là một Girl Number (?) nếu những chữ số của nó thay nhau tăng giảm liên tục. Cụ thể, \(a_1a_2...a_n\) là một Girl Number nếu:

\(a_1 < a_2 ; a_2 > a_3 ; a_3 < a_4 ; ...\) hoặc \(a_1 > a_2 ; a_2 < a_3 ; a_3 > a_4 ; ...\)

Ami "nhờ" CaiWinDao đếm xem trong các số tự nhiên từ \(L\) đến \(R\), có bao nhiêu Girl Number? Vì CaiWinDao bí mất rồi :((, nên cậu ấy đành nhờ các bạn vậy!!!

Input

Dòng đầu chứa hai số nguyên dương \(a, b\) (\(1 \le a, b \le 10^5\)) tương ứng là số chữ số của \(L\) và \(R\).
Dòng thứ hai chứa hai số tự nhiên \(L, R\) (\(0 \le L \le R \le 10^{100000}\)).

Output

In ra số lượng Girl Number trong đoạn từ \(L\) đến \(R\). Vì đáp số có thể hơi lớn nên các bạn chỉ cần in ra số dư của đáp số khi chia cho \(10^9+7\).

Example

Test 1

Input

1 2
8 15

Output

Note

Ở ví dụ 1, các số từ 8 đến 15 đều là Girl Number trừ số 11. Các số thỏa mãn là: 8, 9, 10, 12, 13, 14, 15.

Test 2

Input

4 4
1998 2004

Output

Note

Ở ví dụ 2, các số từ 1998 đến 2004 có 2 chữ số ở giữa bằng nhau nên không số nào thỏa mãn.

Bình luận

Tải bình luận...

Không có bình luận nào.