#include <fstream> 

using namespace std;

ifstream fin( "sandokan.in" );
ofstream fout( "sandokan.out" );

const int MaxN = 5001;
const int Mod = 2000003;

int comb[MaxN][2];

int NchooseK( int n, int k ) {   
  int t = 0;
  for ( int i = 1; i <= n; ++i ) {
	comb[0][1 - t] = 1;
    for ( int j = 1; j <= k; ++j ) {
	  comb[j][t] = (comb[j][1 - t] + comb[j - 1][1 - t]) % Mod;
	}
    t = 1 - t;
  }
  if ( n == 0 ) {
	return 1;
  }
  return comb[k][1 - t];
}

int main() {
  int n, k, c;

  fin >> n >> k;
  c = n;
  while ( n >= k ) {
	n = n / k + n % k;
  }
  k = n - 1;
  n = c - 1;
  printf( "%d %d", n, k );
  fout << NchooseK( n, k );
  fin.close();
  fout.close();
  return 0;
}