B"A Thue-Morse-Radecki-Mateusz sequence (Thorse-Radewoosh sequence in short) is an infinite sequence constructed from a finite sequence mathrm{gen} of length d and an integer m , obtained in the following sequence of steps: For instance, if we pick mathrm{gen} = (0, color{blue}{1}, color{green}{2}) and m = 4 : As you can see, as long as the first element of mathrm{gen} is 0 , each consecutive step produces a sequence whose prefix is the sequence generated in the previous step. Therefore, we can define the infinite Thorse-Radewoosh sequence M_ infty as the sequence obtained by applying the step above indefinitely. For the parameters above, M_ infty = (0, 1, 2, 1, 2, 3, 2, 3, 0, 1, 2, 3, 2, 3, 0, 3, 0, 1, ... ) . Mateusz picked a sequence mathrm{gen} and an integer m , and used them to obtain a Thorse-Radewoosh sequence M_ infty . He then picked two integers l , r , and wrote down a subsequence of this sequence A := ((M_ infty)_l, (M_ infty)_{l+1}, ... , (M_ infty)_r) . Note that we use the 1 -based indexing both for M_ infty and A . Mateusz has his favorite sequence B with length n , and would like to see how large it is compared to A . Let's say that B majorizes sequence X of length n (let's denote it as B geq X ) if and only if for all i in {1, 2, ... , n } , we have B_i geq X_i . He now asks himself how many integers x in the range [1, |A| - n + 1] there are such that B geq (A_x, A_{x+1}, A_{x+2}, ... , A_{x+n-1}) . As both sequences were huge, answering the question using only his pen and paper turned out to be too time-consuming. Can you help him automate his research? The first line contains two integers d and m ( 2 <= q d <= q 20 , 2 <= q m <= q 60 ) -- the length of the sequence mathrm{gen} and an integer used to perform the modular operations. Th"...