n = 2018;
m = 104;
mod = 2^89 - 1;
dp = Table[0, {i, n}, {j, m}];
For[i = 2, i <= n, ++i, Print[i];
  	cur = 2 * PowerMod[3, i - 2, mod];
  	For[j = 1, j <= m, ++j,
   dp[[i]][[j]] = dp[[i - 1]][[j]] + PowerMod[cur, j - 1, mod]];
  	For[p = 0, p < m, ++p,
   		For[a = 0, a <= p, ++a, b = p - a;
    			factmult = Mod[(p!/a!/b!), mod];
    			A = PowerMod[cur, a, mod];
    			B = dp[[i - 1]][[b + 1]];
    			dp[[i]][[p + 1]] += Mod[factmult * A*B , mod];
    			dp[[i]][[p + 1]] = Mod[dp[[i]][[p + 1]], mod];
    ]]];
Print[dp[[n]][[m]]];