1 /**************************************************************  2     Problem: 1089  3     User: rausen  4     Language: Pascal  5     Result: Accepted  6     Time:32 ms  7     Memory:1204 kb  8 ****************************************************************/  9   10 const 11   m : longint = 10000; 12   13 type 14   arr = array[0..10000] of longint; 15   16 var 17   f : array[0..20] of arr; 18   ans : arr; 19   i, n, d : longint; 20   21 operator + (const a : arr; const b : longint) c : arr; 22 var 23   l : longint; 24   25 begin 26   fillchar(c, sizeof(c), 0); 27   for l := 1 to a[0] do 28     c[l] := a[l]; 29   c[1] := c[1] + b; 30   l := 1; 31   while c[l] >= m do begin 32     c[l + 1] := c[l + 1] + c[l] div m; 33     c[l] := c[l] mod m; 34     inc(l); 35   end; 36   l := a[0] + 1; 37   while c[l] = 0 do dec(l); 38   c[0] := l; 39 end; 40   41 operator * (const a : arr; const b : arr) c : arr; 42 var 43   i, j, x, l : longint; 44   45 begin 46   fillchar(c, sizeof(c), 0); 47   for i := 1 to a[0] do 48     for j := 1 to b[0] do begin 49       x := i + j - 1; 50       c[x] := c[x] + a[i] * b[j]; 51       c[x + 1] := c[x + 1] + c[x] div m; 52       c[x] := c[x] mod m; 53     end; 54   l := 0; 55   while l <= a[0] + b[0] + 1 do begin 56     c[l + 1] := c[l + 1] + c[l] div m; 57     c[l] := c[l] mod m; 58     inc(l); 59   end; 60   l := a[0] + b[0] + 1; 61   while c[l] = 0 do dec(l); 62   c[0] := l; 63 end; 64   65 operator - (const a : arr; const b : arr) c :arr; 66 var 67   l, del : longint; 68   69 begin 70   fillchar(c, sizeof(c), 0); 71   l := 1; 72   del := 0; 73   while l <= a[0] do begin 74     c[l] := a[l] - b[l] - del; 75     if c[l] < 0 then begin 76       del := 1; 77       c[l] := c[l] + m; 78     end else del := 0; 79     inc(l); 80   end; 81   l := a[0]; 82   while c[l] = 0 do 83     dec(l); 84   c[0] := l; 85 end; 86   87 procedure refresh(var a : arr); 88 begin 89   fillchar(a, sizeof(a), 0); 90 end; 91   92 function pow(a : arr; x : longint) : arr; 93 var 94   b : arr; 95   96 begin 97   refresh(b); 98   b := b + 1; 99   while x > 0 do begin100     if x and 1 = 1 then b := b * a;101     a := a * a;102     x := x shr 1;103   end;104   exit(b);105 end;106  107 procedure print(a : arr);108 var109   i : longint;110  111 begin112   for i := a[0] downto 1 do begin113     if i <> a[0] then begin114       if a[i] < 1000 then write(0);115       if a[i] < 100 then write(0);116       if a[i] < 10 then write(0);117     end;118     write(a[i]);119   end;120 end;121  122 begin123   readln(n, d);124   refresh(f[0]);125   f[0] := f[0] + 1;126   for i := 1 to d do127     f[i] := pow(f[i - 1], n) + 1;128   if d = 0 then writeln(1) else begin129     ans := f[d] - f[d - 1];130     print(ans);131   end;132 end.