#include <stdio.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>

#define records 1000000

int main() {
	
	int S [ 2 * records + 1 ] , k , i , j ;
	
	int *friends [ 1000000 + 1 ] ;
	
	for ( i = 1 ; i <= 1000000 ; i++ ) {
	
		friends [ i ] = ( int * ) malloc ( sizeof ( int ) * ( 1000000 + 1 ) ) ;
	}
	
	for ( k = 1 ; k <= 2 * records ; k++ ) {
	
		if ( k >= 1 && k <= 55 ) {

			S [ k ] = ( 100003 - 200003 * k + 300007 * k * k * k ) % 1000000 ;
		}
	
		if ( k >= 56 ) {
		
			S [ k ] = ( S [ k - 24 ] + S [ k - 55 ] ) % 1000000 ;
		}
	}
	
	for ( i = 1 ; i <= 1000000 ; i++ ) {
		
		for ( j = 1 ; j <= 1000000 ; j++ ) {
		
			friends [ i ] [ j ] = 0 ;
		}
	}
	
	printf ( "%d\n" , friends [ 334536 ] [ 734565 ] ) ;
	
	for ( i = 1 ; 1 <= 1000000 ; i++ ) {
	
		free ( friends [ i ] ) ;
	}
	
	return 0;
}