Problem 602
Product of Head Counts
Alice enlists the help of some friends to generate a random number, using a single unfair coin. She and her friends sit around a table and, starting with Alice, they take it in turns to toss the coin. Everyone keeps a count of how many heads they obtain individually. The process ends as soon as Alice obtains a Head. At this point, Alice multiplies all her friends’ Head counts together to obtain her random number.
As an illustration, suppose Alice is assisted by Bob, Charlie, and Dawn, who are seated round the table in that order, and that they obtain the sequence of Head/Tail outcomes THHH—TTTT—THHT—H beginning and ending with Alice. Then Bob and Charlie each obtain 2 heads, and Dawn obtains 1 head. Alice’s random number is therefore $2\times 2\times 1 = 4$.
Define $e(n, p)$ to be the expected value of Alice’s random number, where $n$ is the number of friends helping (excluding Alice herself), and $p$ is the probability of the coin coming up Tails.
It turns out that, for any fixed $n$, $e(n, p)$ is always a polynomial in $p$. For example, $e(3, p) = p^3 + 4p^2 + p$.
Define $c(n, k)$ to be the coefficient of $p^k$ in the polynomial $e(n, p)$. So $c(3, 1) = 1$, $c(3, 2) = 4$, and $c(3, 3) = 1$.
You are given that $c(100, 40) \equiv 986699437 \text{ } (\text{mod } 10^9+7)$.
Find $c(10000000, 4000000) \mod 10^9+7$.
抛硬币结果的乘积
爱丽丝正在朋友的帮助下用一枚不公平硬币生成随机数。她和她的朋友围坐在桌子旁，从爱丽丝开始轮流抛掷硬币。每个人都各自记住他们抛出了多少次正面。当爱丽丝抛出正面时，这一流程宣告结束。此时，爱丽丝将她的朋友们所记录的正面次数相乘，作为她的随机数。
举例来说，假如爱丽丝找来鲍勃、查理和道恩帮忙，他们就按照这个顺序坐在桌子旁边，抛掷硬币的结果是序列THHH—TTTT—THHT—H，从爱丽丝开始并且到爱丽丝结束。鲍勃和查理各自抛出了2次正面，而道恩则抛出了1次正面。因此爱丽丝的随机数就是$2\times 2\times 1 = 4$。
记$e(n, p)$为帮忙的朋友数目为$n$（除爱丽丝自己以外）且硬币抛出反面概率为$p$时，爱丽丝所获得的随机数的期望值。
事实上，对于任意固定的$n$，$e(n, p)$总是$p$的一个多项式。例如$e(3, p) = p^3 + 4p^2 + p$。
定义$c(n, k)$为多项式$e(n, p)$中$p^k$项的系数。因此$c(3, 1) = 1$，$c(3, 2) = 4$，而$c(3, 3) = 1$。
已知$c(100, 40) \equiv 986699437 \text{ } (\text{mod } 10^9+7)$。
求$c(10000000, 4000000) \mod 10^9+7$。