Gửi bài giải
Điểm:
0,65 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C++, Pascal, Python
Cho một số ~a~ và ~b~. Ta tiến hành xây dựng số mới ~c~ bằng cách sử dụng lần lượt các chữ số của số số ~a~ từ trái sang phải. Ở mỗi lượt có thể chọn 2 bên trái hoặc phải số ~c~ (trừ lượt đầu tiên) để đặt chữ số hiện tại vào. Ví dụ số ~c~ đang là ~38182~, đang xét số ~1~ thì sau khi đặt vào bên trái sẽ trở thành ~138182~, tương tự bên phải sẽ là ~381821~. Số ~c~ mới được phép có số 0 xuất hiện ở đầu.
Số được gọi là đẹp nếu số đó không vượt quá số ~b~. Hãy tính tổng các số đẹp được xây dựng theo cách trên, 2 số được gọi là khác nhau nếu cách xây dựng số đấy khác nhau, kể cả giá trị có bằng nhau.
Input
- Dòng đầu tiên gồm số tự nhiên ~T \le 50~ là số lượng test.
- Mỗi nhóm dòng tiếp theo gồm xâu ~a~ với ~|a| \le 500~ chỉ gồm các chữ số là số tự nhiên ~b \le 10^{500}~.
Output
- Với mỗi test in ra một số là tổng các số đẹp modulo ~10^9+7~.
Sample Test
Input:
1
1013
3000
Output:
3242