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, ldots, 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, ldots, N – 1}~ sao cho ~(X_i + X_{i+1}) mod 5 = 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 leq i leq j leq N~ và ~X_i oplus X_{i+1} oplus ldots 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~.
Input
Vào từ file văn bản PNUM.INP:
-
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 leq k leq 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 leq T leq 50,000)~.
-
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 leq L leq H leq 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.
Output
Ghi ra file văn bản PNUM.OUT:
- 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 ~1,000,000,007~ tương ứng với trường hợp test trong dữ liệu đầu vào.
Scoring
Subtask Điểm Giới hạn 1 ~12%~ ~T leq 10~ và ~H leq 10^6~ 2 ~12%~ ~T leq 10~; ~H leq 10^{18}~ và ~k = 1~ 3 ~12%~ ~H leq 10^{18}~ và ~k = 1~ 4 ~12%~ ~k = 1~ 5 ~20%~ ~T leq 10~; ~H leq 10^9~ và ~k = 2~ 6 ~16%~ ~L~ là luỹ thừa của 10; ~H = 10 times L – 1~ và ~k = 2~ 7 ~16%~ Không có ràng buộc nào thêm
Sample Input 1
1 3 1 10 100 105 111239 111245
Sample Output 1
1 5 12
Sample Input 2
2 3 1 10 100 105 111239 111245
Sample Output 2
1 7 30
Notes
Trong ví dụ thứ nhất:
-
Trường hợp test thứ nhất: ~W(1) = W(2) = W(3) = W(4) = W(5) = W(6) = W(7) = W(8) = W(9) = 0~, ~W(10) = 1~, nên kết quả là ~0^1 + 0^1 + 0^1 + 0^1 + 0^1 + 0^1 + 0^1 + 0^1 + 0^1 + 1^1 = 1~.
-
Trường hợp test thứ hai: ~W(100) = 0~, ~W(101) = 2~, ~W(102) = 1~, ~W(103) = 1~, ~W(104) = 1~, ~W(105) = 0~, nên kết quả là ~0^1 + 2^1 + 1^1 + 1^1 + 1^1 + 0^1 = 5~.
-
Trường hợp test thứ ba: ~W(111239) = 0~, ~W(111240) = 3~, ~W(111241) = 0~, ~W(111242) = 2~, ~W(111243) = 2~, ~W(111244) = 3~, ~W(111245) = 2~, nên kết quả là ~0^1 + 3^1 + 0^1 + 2^1 + 3^1 + 2^1 = 12~.
Trong ví dụ thứ hai:
-
Trường hợp test thứ nhất: Kết quả là ~0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 0^2 + 1^2 = 1~.
-
Trường hợp test thứ hai: Kết quả là ~0^2 + 2^2 + 1^2 + 1^2 + 1^2 + 0^2 = 7~.
-
Trường hợp test thứ ba: Kết quả là ~0^2 + 3^2 + 0^2 + 2^2 + 3^2 + 2^2 = 30~.