program sandokan;  
  var f,g:text;  
          fact:array[1..5001] of longint;  
          n,k:longint;  
          constanta:int64;  
          prime:array[1..5001] of longint;  
         nrprime:longint;  
         howmany:array[1..5001] of longint;  
 .   
    
  
 
   
  procedure iofile;  
  begin  
          assign(f,'sandokan.in');reset(f);  
          assign(g,'sandokan.out');rewrite(g);  
          readln(f,n,k);  
          constanta:=2000003;  
          close(f);  
  end;  
    
    
    
  function prim(x:longint):boolean;  
  var d:longint;  
  begin  
         if (x=1) or (x=0) then prim:=false else  
                  begin  
                          prim:=true;  
                          for d:=2 to trunc(sqrt(x)) do  
                                  if x mod d=0 then  
                                          begin  
                                                  prim:=false;  
                                                  exit;  
                                          end;  
                  end;  
  end;  
    
    
  procedure det_prime;  
  var i:longint;  
  begin  
          for i:=1 to n do  
                  if prim(i) then  
                          begin  
                                  inc(nrprime);  
                                  prime[nrprime]:=i;  
                          end;  
  end;  
    
    
  function logaritmic(a,b:int64):int64;  
  var i,pow,current,rez:int64;  
  begin  
          rez:=1;  
          pow:=0;  
          current:=a;  
          while (1 shl (pow))<=b do  
                  begin  
                          if ((1 shl (pow)) and b)<>0 then  
                                  rez:=(rez*current) mod constanta;  
                          inc(pow);  
                          current:=(current*current) mod constanta;  
                  end;  
          logaritmic:=rez;  
  end;  
  procedure prel;  
  var npart,countop,ind,exp,x,rest,rez:int64;  
          i:longint;  
  begin  
          countop:=0;  
          npart:=n;  
          while npart>=k do  
                  begin  
                          inc(countop);  
                          {for i:=npart-k+1 to npart-1 do  
                                  inc(howmany[i]);}  
                          npart:=npart-k+1;  
                end;  
          fillchar(fact,sizeof(fact),0);  
         {for i:=2 to k-1 do  
                 howmany[i]:=howmany[i]-countop;}
	for i:=2 to n-1 do
		inc(howmany[i]);
	for i:=2 to npart-1 do
	dec(howmany[i]);
	for i:=2 to (n-npart) do
	dec(howmany[i]);  
      for i:=2 to n-1 do  
                 if howmany[i]<>0 then  
                 begin  
                          ind:=1;  
                          x:=i;  
                          while (ind<=nrprime)and(x<>1) do  
                                begin  
                                          exp:=0;  
                                         while (x mod prime[ind])=0 do  
                                                  begin  
                                                          x:=x div prime[ind];  
                                                          inc(exp);  
                                                  end;  
                                         fact[prime[ind]]:=fact[prime[ind]]+  
                                         howmany[i]*exp;  
                                        inc(ind);  
                                  end;  
                  end;  
          rez:=1;  
          for i:=1 to n do  
                  if fact[i]<>0 then  
                          begin  
                                  rest:=logaritmic(i,fact[i]);  
                                  rez:=(rez*rest) mod constanta;  
                          end;  
          writeln(g,rez);  
          close(g);  
  end;  
    
    
  begin  
          iofile;  
          det_prime;  
          prel;  
  end.