Girl Number

Người ta thường nói tình yêu cũng giống như điểm Codeforces, có lúc thăng hoa, có lúc chạm đáy. Một ngày nọ, Ami ngồi ngẩn ngơ viết ra một dãy chữ số. Nhìn lại, cậu nhận ra các chữ số cứ lần lượt tăng rồi giảm, giảm rồi lại tăng, chẳng khác nào biểu đồ cảm xúc của mình.

Thấy khá thú vị, Ami quyết định gọi những số như vậy là Girl Number và mang đi đố CaiWinDao.

Một số nguyên không âm có dạng \(a_1a_2\dots a_n\) được gọi là Girl Number nếu các chữ số của nó luân phiên tăng và giảm. Cụ thể, số đó phải thỏa mãn một trong hai dạng sau:

hoặc

Yêu cầu. Cho hai số nguyên không âm \(L\) và \(R\). Hãy đếm xem có bao nhiêu Girl Number nằm trong đoạn \([L,R]\).

\InputFile

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

\OutputFile

In ra số lượng Girl Number trong đoạn \([L,R]\).

Vì đáp số có thể rất lớn, hãy in ra kết quả theo modulo \(1000000007\).

\Examples

\beginexample
\exmp
1 2
8 15

7

\exmp
4 4
1998 2004

0

\endexample

\Note

Trong ví dụ thứ nhất, mọi số từ \(8\) đến \(15\) đều là Girl Number, ngoại trừ số \(11\). Do đó đáp án là \(7\).

Trong ví dụ thứ hai, các số trong đoạn đều có hai chữ số ở giữa bằng nhau, nên không thể tạo thành một dãy luân phiên tăng và giảm. Vì vậy không có số nào thỏa mãn.

\Scoring

• (30%) \(R \le 10^6\).
• (30%) Số chữ số của \(R\) không vượt quá \(18\).
• (40%) Không có ràng buộc bổ sung.

\endproblem