Recover the Sequence#2822

Recover the Sequence

1 second

64 megabytes

Easy

Merge sort is one of the classical sorting algorithms. It divides the input array into two halves, recursively sorts each half, and then merges the two sorted halves.

In this problem, the merge sort algorithm sorts an array of integers in ascending order. The exact behavior is described by the following pseudocode:

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 from $1$ to $n$ was lost because the hard disk failed. Fortunately, this sequence had been sorted using the algorithm above, and the debug information containing only ones ( $1$ ) and twos ( $2$ ) was saved on another disk. Based on the given sequence length $n$ and the debug information, you need to restore the original sequence of integers.

Input

The first line contains the number $t$ of test cases. Each test consists of two lines. The first line of each test contains the length of the original sequence $n$ ( $2 \leq n \leq 10000$ 2 \leq n \leq 10000). The second line contains the debug sequence— a string of $1$ s and $2$ s — produced by the merge sort algorithm for the original sequence. Lines are separated using the "\n" character.

Output

Instead of outputting the entire sequence, you should only compute and print its checksum, which is 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

Examples

In the first example, $n$ is $2$ and the debug sequence is $1$ . The original sequence could be $1$ $2$ or $2$ $1$ . The debug sequence tells us the first number is less than the second so the sequence must be $1$ $2$ . Its checksum is $994$ .

In the second example, $n$ is $2$ and the debug sequence is $2$ . This time, the original sequence is $2$ $1$ .

In the third example, $n$ is $4$ and the debug sequence is $12212$ . The original sequence is $2$ $4$ $3$ $1$ .

Example 1