Facebook Hacker Cup 2012 Round 1 Solutions: Recover the Sequence

Problem:

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 1 through N was lost to a hard drive failure. Luckily, that sequence had been sorted by the above algorithm and the debug sequence of 1s and 2s was recorded on a different disk. You will be given the length N of the original sequence, and the debug sequence. Recover the original sequence of integers.
Input
The first line of the input file contains an integer T. This is followed by T test cases, each of which has two lines. The first line of each test case contains the length of the original sequence, N. The second line contains a string of 1s and 2s, the debug sequence produced by merge sort while sorting the original sequence. Lines are separated using Unix-style ("\n") line endings.
Output
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

Constraints
5 ≤ T ≤ 20
2 ≤ N ≤ 10000
Examples
In the first example, N is 2 and the debug sequence is 1. The original sequence was 1 2 or 2 1. The debug sequence tells us that the first number was smaller than the second so we know the sequence was 1 2. The 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.

Solution:
Solution is easy. You just have to re-implement the provided algorithm in the language of your choice, with the only exception: instead of comparing arr1[0] to arr2[0] and outputting '1' or '2' depending on the result of the comparison, we append the result with the arr1[0] if the debug sequence [0] is '1', and arr2[0] otherwise. Just do not forget to strip the debug sequence of the 0th element afterwards.

Feed the sorted sequence of 1..N to the re-implemented algorithm. The algorithm will produce a permutation of the input. In this permutation, for i from 0 to N-1, permutation[i] is the position of element with the value of i+1 in the original sequence.

Having the original sequence, we only have to apply the checksum function to it, and output the result.