Farmer John wrote down N (1≤N≤300) digits on pieces of paper. For each i∈[1,N], the ith piece of paper contains digit ai (1≤ai≤9).

The cows have two favorite integers A and B (1≤A≤B<10¹⁸), and would like you to answer Q (1≤Q≤5⋅10⁴) queries. For the ith query, the cows will move left to right across papers li…ri (1≤li≤ri≤N), maintaining an initially empty pile of papers. For each paper, they will either add it to the top of the pile, to the bottom of the pile, or neither. In the end, they will read the papers in the pile from top to bottom, forming an integer. Over all 3ri−li+1 ways for the cows to make choices during this process, count the number of ways that result in the cows reading an integer in [A,B] inclusive, and output this number modulo 10⁹+7.

#5508 upload 17 done 4 how_to_reg 4

Piling Papers timer 1s memory 512MB

#5508

Piling Papers 1s 512MB