记录编号	26908	评测结果	AAAAAAAAAA
题目名称	01环	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	9.023 s
提交时间	2011-07-29 15:38:23	内存使用	30.72 MiB

{01环 NOI模拟赛出题
 计数 动态规划
 Author: yangbohua
 Time: 2011-07-27}
 
program ring01;
const
  maxn=2001;
var
  p:array[0..maxn,0..maxn] of int64;
  r,expp:array[0..maxn] of int64;
  n,k,t,que,i,j,g,mm:longint;
  ans:int64;

function mod_exp(x:longint):int64;
var
  temp,ret:int64;
  y:longint;
begin
  temp:=x;
  y:=mm-2;
  ret:=1;
  while y>0 do
  begin
    if y and 1=1 then ret:=(ret*temp) mod mm;
    temp:=(temp*temp) mod mm;
    y:=y shr 1;
  end;
  exit(ret);
end;

begin
  assign(input,'01ring.in');
  reset(input);
  assign(output,'01ring.out');
  rewrite(output);

  readln(t,mm);
  for i:=1 to 2000 do
    expp[i]:=mod_exp(i);
  for que:=1 to t do
  begin
    readln(n,k);
    if n<k then k:=n;
    p[1,0]:=1;
    for i:=1 to n do
    begin
      p[i+1,0]:=0;
      if i-1<k then g:=i-1 else g:=k;
      for j:=0 to g do
      begin
        p[i+1,0]:=(p[i+1,0]+p[i,j]) mod mm;
        p[i+1,j+1]:=p[i,j];
      end;
    end;
    for i:=1 to n do
    begin
      r[i]:=0;
      if n mod i=0 then
      begin
        if i-1<k then g:=i-1 else g:=k;
        for j:=0 to g do
          r[i]:=(r[i]+p[i,j]*(j+1)) mod mm;
      end;
    end;
    if k=n then ans:=1 else ans:=0;
    for i:=1 to n do
      if n mod i=0 then
      begin
        j:=i*2;
        while j<=n do
        begin
          r[j]:=(r[j]-r[i]+mm) mod mm;
          j:=j+i;
        end;
        ans:=(ans+r[i]*expp[i]) mod mm;
      end;
    writeln(ans);
  end;

  close(input);
  close(output);
end.