Merge sort is one of the classic sorting algorithms. It divides the input array into two halves, recursively sorts each half, then merges the two sorted halves. In this problem merge sort is used to sort an array of integers in ascending order. The exact behavior is given by the following pseudo-code: function merge_sort(arr): n = arr.length() if n <= 1: return arr // arr is indexed 0 through n-1, inclusive mid = floor(n/2) first_half = merge_sort(arr\[0..mid-1\]) second_half = merge_sort(arr\[mid..n-1\]) return merge(first_half, second_half)function merge(arr1, arr2): result = \[\] while arr1.length() > 0 and arr2.length() > 0: if arr1\[0\] < arr2\[0\]: print '1' // for debugging result.append(arr1\[0\]) arr1.remove_first() else: print '2' // for debugging result.append(arr2\[0\]) arr2.remove_first() result.append(arr1) result.append(arr2) return result A very important permutation of the integers \textbf{1} through \textbf{n} was lost to a hard drive failure. Luckily, that sequence had been sorted by the above algorithm and the debug sequence of \textbf{1}s and \textbf{2}s was recorded on a different disk. You will be given the length \textbf{n} of the original sequence, and the debug sequence. Recover the original sequence of integers. \InputFile The first line contains the number \textbf{t} of test cases. Each test case consists of two lines. The first line of each test case contains the length of the original sequence \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{10000}). The second line contains a string of \textbf{1}s and \textbf{2}s, the debug sequence produced by merge sort while sorting the original sequence. Lines are separated using Unix-style ("\textbf{\textbackslash n}") line endings. \OutputFile To avoid having to upload the entire original sequence, output an integer checksum of the original sequence, calculated by the following algorithm: function checksum(arr): result = 1 for i=0 to arr.length()-1: result = (31 * result + arr\[i\]) mod 1000003 return result \textbf{Examples} In the first example, \textbf{n} is \textbf{2} and the debug sequence is \textbf{1}. The original sequence was \textbf{1} \textbf{2} or \textbf{2} \textbf{1}. The debug sequence tells us that the first number was smaller than the second so we know the sequence was \textbf{1} \textbf{2}. The checksum is \textbf{994}. In the second example, \textbf{n} is \textbf{2} and the debug sequence is \textbf{2}. This time the original sequence is \textbf{2 1}. In the third example, \textbf{n} is \textbf{4} and the debug sequence is \textbf{12212}. The original sequence is \textbf{2} \textbf{4} \textbf{3} \textbf{1}.