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.


Specifications
   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 (2 ≤ N ≤ 10000). 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
   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.


Problem information
Time Limit: 1 seconds
Memory Limit: 64 MB

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

void normal_merge_sort(int arr[], int n);
void normal_merge(int arr1[], int n1, int arr2[], int n2);
void solve_merge_sort(int arr[], int n);
void solve_merge(int arr1[], int n1, int arr2[], int n2);
int checksum(int arr[], int n);

int res[100000], inv[100000];
int memory[100000];

char input[8000000]; int input_st;

int main(){
int i,j,k,N;
int sum;
int size, count = 0;

scanf("%d",&size);
while(size--){
   scanf("%d%s",&N,input);
   input_st = 0;
   
   rep(i,N) res[i] = i;
   solve_merge_sort(res, N);

   rep(i,N) inv[res[i]] = i;
   rep(i,N) res[i] = inv[i]+1;

   sum = checksum(res,N);
/*    normal_merge_sort(res, N); puts("");*/
   printf("Case #%d: %d\n",++count,sum);
}

return 0;
}


void normal_merge_sort(int arr[], int n){
int mid;

if(n <= 1) return;
mid = n/2;

normal_merge_sort(arr, mid);
normal_merge_sort(arr+mid, n-mid);
normal_merge(arr, mid, arr+mid, n-mid);
}

void normal_merge(int arr1[], int n1, int arr2[], int n2){
int i, size = 0;
int st1 = 0, st2 = 0;

while(st1 < n1 && st2 < n2){
   if(arr1[st1] < arr2[st2]){
     putchar('1');
     memory[size++] = arr1[st1++];
   } else {
     putchar('2');
     memory[size++] = arr2[st2++];
   }
}

while(st1 < n1) memory[size++] = arr1[st1++];
while(st2 < n2) memory[size++] = arr2[st2++];
rep(i,size) arr1[i] = memory[i];
}

void solve_merge_sort(int arr[], int n){
int mid;

if(n <= 1) return;
mid = n/2;

solve_merge_sort(arr, mid);
solve_merge_sort(arr+mid, n-mid);
solve_merge(arr, mid, arr+mid, n-mid);
}

void solve_merge(int arr1[], int n1, int arr2[], int n2){
int i, size = 0;
int st1 = 0, st2 = 0;

while(st1 < n1 && st2 < n2){
   if(input[input_st++]=='1'){
     memory[size++] = arr1[st1++];
   } else {
     memory[size++] = arr2[st2++];
   }
}

while(st1 < n1) memory[size++] = arr1[st1++];
while(st2 < n2) memory[size++] = arr2[st2++];
rep(i,size) arr1[i] = memory[i];
}

int checksum(int arr[], int n){
int i, res = 1;
rep(i,n) res = (31 * res + arr[i]) % 1000003;
return res;
}