Hi there! Imagine you're participating in codechef long challenge and you see a problem from chemthan asking you to calculate some sums of powers like 1^p + 2^p + ... + n^p for all p from 0 to k. You immediately understand what's going on here and take Faulhaber's formula from your wide pants, do ya? Just take a look at it!

Beautiful, right? Wrong! This formula is dumb and it's hard to understand and remember! Why would you ever think about Bell's number on any contest which lasts less than a week? And what the hell are those Bell's numbers?! Here is what you should do:

Let S_p = 1^p + ... + n^p. Consider its exponential generating function (EGF):

Now you can simply find S₀, ..., S_k by finding inverse series for and multiplying it with . Enjoy your power sums without Stirling and/or Bell's numbers!

Exercise: Solve this problem in .

P.S. Yes, you basically perform the same calculations as in Faulhaber's formula, but now you hopefully understand what you're doing.