Số siêu đối xứng

Một dãy các chữ số từ $0$ đến $9$ được gọi là dãy đối xứng nếu như đọc từ trái sang phải hay từ phải sang trái đều thu được kết quả giống nhau. Ví dụ như dãy rỗng và hai dãy $010$, $0110$ là các dãy đối xứng, còn các dãy $123$, $4449$ không phải là dãy đối xứng.

Với dãy $S$ độ dài $k$, các kí tự được đánh số từ $1$ đến $k$. Kí hiệu một dãy con của $S$ gồm các kí tự liên tiếp từ vị trí $a$ đến vị trí $b$ là $S(a,b)$ (giả thiết nếu $a>b$ thì $S(a,b)$ là dãy rỗng), dãy $S$ được định nghĩa là dãy siêu đối xứng nếu đồng thời thỏa mãn các điều kiện sau:

• $S(1,k)$ là dãy đối xứng;
• $S(1,\lfloor k/2\rfloor )$ là dãy đối xứng, trong đó kí hiệu $\lfloor x\rfloor$ là số nguyên lớn nhất không vượt quá $x$;
• $S(k-\lfloor k/2\rfloor +1,k)$ là dãy đối xứng.

Ví dụ các dãy $0$, $11$, $22322$, $454454$ là các dãy siêu đối xứng, còn dãy $990099$ không phải là dãy siêu đối xứng.

Một dãy được gọi là gần siêu đối xứng nếu như tồn tại một cách hoán đổi vị trí các phần tử của nó để thu được một dãy siêu đối xứng. Đương nhiên, một dãy siêu đối xứng cũng đồng thời là một dãy gần siêu đối xứng.

Một số nguyên dương $d$ được gọi là số gần siêu đối xứng nếu như coi biểu diễn thập phân của nó như một dãy các chữ số từ $0$ đến $9$ (không có trường hợp dãy bắt đầu bởi chữ số $0$) thì dãy biểu diễn đó là một dãy gần siêu đối xứng. Lưu ý là sau khi hoán đổi vị trí các phần tử, dãy thu được có thể bắt đầu bởi chữ số $0$. Ví dụ, $d=9505000$ là số gần siêu đối xứng vì tồn tại một cách hoán đổi vị trí các phần tử của dãy các chữ số biểu diễn $d$ thành một dãy siêu đối xứng $0509050$.

Yêu cầu: Cho hai số nguyên dương $p$ và $q$ $(p\le q)$, hãy tìm số lượng các số nguyên gần siêu đối xứng nằm trong khoảng từ $p$ đến $q$ (khoảng bao gồm cả $p$ và $q$).

Dữ liệu vào

Hai số nguyên $p$ và $q$ cách nhau bởi dấu cách.

Dữ liệu ra

In ra duy nhất một số là phần dư của số lượng số gần siêu đối xứng tìm được trong phép chia cho ${10}^9+7$.

Ràng buộc

• $1\le p\le q\le {10}^{50000}$.

Subtasks

• Subtask 1 ($20\%$ số test, $20\%$ số điểm): $1\le p\le q\le {10}^5$;
• Subtask 2 ($30\%$ số test, $30\%$ số điểm): $p={10}^{k-1}$, $q={10}^k-1$, $2\le k\le 18$;
• Subtask 3 ($30\%$ số test, $30\%$ số điểm): $1\le p\le q\le {10}^{18}$;
• Subtask 4 ($20\%$ số test, $20\%$ số điểm): $1\le p\le q\le {10}^{50000}$.

Ví dụ