Xây dựng số

Xem dạng PDF

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