100th degree polynomial $P(2^k)=k$ for $k=0,1,…100$

I sometimes see this kind of question, but I completely forgot how to solve it. Could anyone solve it for me?

-
See this formula for $P(x)$: math.stackexchange.com/questions/577448/… The coefficient of $x^{100}$ in $l_i(x) = \prod_{0 \le k \le 100, k \ne i} \frac{x - 2^k}{2^i - 2^k}$ is $c_i = \prod_{0 \le k \le 100, k \ne i} \frac{1}{2^i - 2^k}$. The leading coefficient of $P(x)$ is $\sum_{i=0}^{100} i c_i$. I asked Mathematica for help, and I got a number is between $-10^{-1521}$ and $-10^{1520}$. Presumably, there's another approach to the question that doesn't require something like Mathematica. –  Steve Kass Nov 23 '13 at 4:18
Generalize the problem in the obvious way to a degree $d$ polynomial $P_d(x)$ with $d+1$ prescribed values. Numerical experimentation indicates that the leading coefficient of $P_d(x)$ equals $(-1)^{d-1}/2^{d(d-1)/2}(2^d-1)$. –  Greg Martin Nov 23 '13 at 4:50
Thanks for your nice answers. Is it possible to solve this with some problem-solving technique other than experimentation? Since I think there was such a technique, I really want to remember what it was. If there doesn't exist such stuff, i guess experimentation is the best way. –  user12345 Nov 23 '13 at 5:08