#include<iostream>
#include<fstream>
using namespace std;
int a[1000001],n,SOL;
void mergesort(int st,int dr)
{   SOL++;
    if(st==dr) return;
    if(a[(st+dr)/2]<=a[(st+dr)/2+1]) return;
    mergesort(st,(st+dr)/2);
    mergesort((st+dr)/2+1,dr);
}
int cont(int k)
{int i;
for(i=1;i<k;i++)
    if(a[i]==a[k])
        return 0;
    return 1;
}

void back(int k)
{int i;
for(i=1;i<=n;i++)
{a[k]=i;
if(cont(k))
    {if(k==n)
        mergesort(1,n);
    else
        back(k+1);}
}}
int main()
{
    ifstream f("mergesort.in.txt");
    f>>n;
    f.close();
    back(1);
    ofstream g("mergesort.out.txt");
    g<<SOL%1000003;
    g.close();
    return 0;
}