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ể, a1a2...an là một Girl Number nếu:
a1 < a2 ; a2 > a3 ; a3 < a4 ; ... hoặc a1 > a2 ; a2 < a3 ; a3 > a4 ; ...
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!!!
Dữ liệu vào:
Dòng đầu chứa 2 số nguyên dương a, b (1 <= a, b <= 100000) tương ứng là số chữ số của L và R.
Dòng thứ hai chứa 2 số tự nhiên L, R (0 <= L <= R <= 10100000).
Kết quả:
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 cho 109+7.
Ví dụ
Input
1 2
8 15
Output
7
Input
4 4
1998 2004
Output
0
Giải thích
Ở ví dụ 1 , các số từ 8 đến 15 đều là Girl Number trừ 11.
Ở 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.