Số nguyên dương

Thầy giáo Lê rất yêu thích các bài toán số học và dãy số. Thầy định nghĩa trọng số của một số nguyên dương $X$ (ký hiệu là $W(X)$) như sau:

• Đầu tiên, thầy Lê biểu diễn $X$ thành dãy các chữ số của nó trong hệ cơ số 10, thu được dãy $X_1,X_2,\dots ,X_N$ với $N$ là số chữ số của $X$;
• Nếu dãy chữ số của $X$ có chứa hai phần tử đứng cạnh nhau có tổng chia hết cho 5, nghĩa là tồn tại $i\in \{1,2,\dots ,N-1\}$ sao cho $(X_i+X_{i+1})mod5=0$, thì $W(X)=0$;
• Ngược lại, $W(X)$ chính là số lượng dãy con gồm các phần tử liên tiếp trong dãy chữ số của $X$ mà có kết quả XOR các phần tử bằng 0. Cụ thể, $W(X)$ là số lượng cặp $(i,j)$ thoả mãn $1\le i\le j\le N$ và $X_i\oplus X_{i+1}\oplus \dots \oplus X_j=0$, với $\oplus$ là phép toán XOR giữa hai số tự nhiên.

Nhắc lại, với hai số tự nhiên $a$ và $b$, phép toán $a\oplus b$ là phép toán XOR từng bit tương ứng của $a$ và $b$ trong biểu diễn hệ nhị phân của chúng.

Ví dụ:

• $W(1234)=0$ vì chứa hai chữ số 2 và 3 cạnh nhau có tổng chia hết cho 5;
• $W(122103)=5$ vì không có hai chữ số nào cạnh nhau có tổng chia hết cho 5, đồng thời dãy chữ số của nó có 5 dãy con gồm các phần tử liên tiếp là $(2,2)$, $(1,2,2,1)$, $(1,2,2,1,0)$, $(0)$ và $(2,1,0,3)$ có XOR các phần tử bằng 0;
• $W(3456)=0$ vì dãy chữ số của nó không có dãy con nào có XOR các phần tử bằng 0.

Yêu cầu: Cho số nguyên dương $k$ và các số nguyên dương $L,H$. Hãy tính tổng lũy thừa $k$ của trọng số của tất cả các số nguyên dương nằm trong phạm vi $[L,H]$, nghĩa là tính ${\sum }_{X=L}^H(W(X){)}^k$.

Dữ liệu vào

• Dòng đầu chứa một số nguyên dương $k$ là số lũy thừa trong tổng cần tính ($1\le k\le 2$).
• Dòng thứ hai chứa một số nguyên dương $T$ là số lượng trường hợp test ($1\le T\le 50000$).
• Mỗi dòng trong số $T$ dòng tiếp theo chứa hai số nguyên dương $L$ và $H$ mô tả một trường hợp test ($1\le L\le H\le {10}^{1000}$).

Dữ liệu bảo đảm tổng số chữ số của tất cả các số $L$ và $H$ trong một file dữ liệu vào không vượt quá ${10}^5$. Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

Gồm $T$ dòng, mỗi dòng chứa một số nguyên là phần dư của kết quả tìm được trong phép chia cho $1000000007$ tương ứng với trường hợp test trong dữ liệu đầu vào.

Ràng buộc

• $1\le k\le 2$; $1\le T\le 50000$.
• $1\le L\le H\le {10}^{1000}$.
• Tổng số chữ số của tất cả các số $L$ và $H$ trong một file dữ liệu vào không vượt quá ${10}^5$.

Subtasks

• Subtask 1 ($12\%$ số điểm): $T\le 10$ và $H\le {10}^6$.
• Subtask 2 ($12\%$ số điểm): $T\le 10$; $H\le {10}^{18}$ và $k=1$.
• Subtask 3 ($12\%$ số điểm): $H\le {10}^{18}$ và $k=1$.
• Subtask 4 ($12\%$ số điểm): $k=1$.
• Subtask 5 ($20\%$ số điểm): $T\le 10$; $H\le {10}^9$ và $k=2$.
• Subtask 6 ($16\%$ số điểm): $L$ là luỹ thừa của 10; $H=10\times L-1$ và $k=2$.
• Subtask 7 ($16\%$ số điểm): không có ràng buộc nào thêm.

Ví dụ