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

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~.