#include <cstdio>
#include <algorithm>
using namespace std;

#define N 2005
#define K 2005
#define MOD 1000003
enum { A,B };
#define add(r,v) r=((r)+(v))%MOD
#define sub(r,v) r=((r)-(v)%MOD+MOD)%MOD
#define mul(r,v) r=((r)*(v))%MOD

typedef long long ll;
int n,k;
ll row_tbl[N][2][K],row_done[N][2][K];
ll aperiodic_tbl[N],aperiodic_done[N];
ll periodic_tbl[N],periodic_done[N];
ll inv[N];

ll pow_mod(ll a, ll k) {
  ll r=1,t=a;
  while(k) {
    if (k&1) mul(r,t);
    k>>=1;
    mul(t,t);
  }
  return r;
}

ll row(int pos, int last, int con) {
  if (pos==1) return last==A&&con==1;

  ll& res=row_tbl[pos][last][con];
  if (row_done[pos][last][con]) return res;
  row_done[pos][last][con]=1;
  res=0;

  if (con==1) {
    for (int ncon=1;ncon<=k;++ncon) add(res,row(pos-1,1-last,ncon));
  } else {
    res=row(pos-1,last,con-1);
  }
  return res;
}

ll solve_aperiodic(int n) {
  if (k>=n) return pow_mod(2,n);

  ll& res=aperiodic_tbl[n];
  if (aperiodic_done[n]) return res;
  aperiodic_done[n]=1;
  res=0;

  for (int con=1;con<=k;++con) add(res,row(n,B,con)*2*con);
  //  printf("aperiodic[%d][%d]=%lld\n",n,k,res);
  return res;
}

ll solve_periodic(int n) {
  if (n==1) return 2;

  ll& res=periodic_tbl[n];
  if (periodic_done[n]) return res;
  periodic_done[n]=1;
  res=solve_aperiodic(n);

  if (k>=n) res-=2;
  for (int i=2;i*i<=n;++i) {
    if (n%i==0&&i!=n) {
      sub(res,solve_periodic(i));
      if (n/i!=i&&n/i!=n) sub(res,solve_periodic(n/i));
    }
  }
  //  printf("periodic[%d][%d]=%lld\n",n,k,res);
  return res;
}

int main() {
  for (int i=0;i<N;++i) inv[i]=pow_mod(i,MOD-2);

  scanf("%d%d",&n,&k);

	ll ans=0;
	for (int i=2;i*i<=n;++i)
		if (n%i==0) {
			add(ans,solve_periodic(i)*inv[i]);
			if (n/i!=i) add(ans,solve_periodic(n/i)*inv[n/i]);
		}
	if (k>=n) add(ans,2);
	if (n!=1) add(ans,solve_periodic(n)*inv[n]);
	printf("%lld\n",ans);
}