Constructing numbers - MarisaOJ: Marisa Online Judge

Given two numbers

a

$a$ and

b

$b$ , we proceed to construct a new number

c

$c$ by using the digits of

a

$a$ one by one from left to right. In each turn, we can choose to place the current digit to the left or right of the current

c

$c$ (excluding the first turn). For example, if

c

$c$ is currently

38182

$38182$ and we are considering the digit

1

$1$ , placing it to the left will make

138182

$138182$ , and placing it to the right will make

381821

$381821$ . The newly formed number

c

$c$ is allowed to have the digit

0

$0$ at the beginning. A number is considered beautiful if it does not exceed the value of

b

$b$ . Calculate the sum of all beautiful numbers constructed in this way. Two numbers are considered different if their construction methods differ, even if they have the same value. ### Input - The first line contains a natural number

T

$T$ , representing the number of test cases. - Each group of lines that follows consists of a string

a

$a$ , containing only digits, and a natural number

b

$b$ . ### Output - For each test case, print a number representing the sum of beautiful numbers modulo

10^{9} + 7

$10^9+7$ . ### Constraints -

T \leq 50

$T \le 50$ . -

| a | \leq 500

$|a| \le 500$ . -

b \leq 10^{500}

$b \le 10^{500}$ . ### Example Input:

110133000

$1 1013 3000$

Output:

3242

$3242$

Digit DP
	Unlucky number
	Digit Sum
	Divisible
	Prime digit sum
	Non-palindrome number
	Yet another XOR problem
	Taboo substring
	Balanced number
	Equation
	Beautiful number
	Constructing numbers

Topic

Dynamic Programming

Rating

2200

Solution (0)

Solution