Problem #337
Tuta Puta
There are k different types of characters in Tuta-Puta language. You start adding these characters to an empty string. At every addition, you choose any one of these k characters with equal probability. You stop when every type of character occurs odd number of times in the string.
What is the expected length of your string if k=2282023 ?
Given that the answer is of the form \frac{p}{q}, where the greatest common divisor of p and q is 1, find the value of x where x \equiv p \cdot q^{-1} \text{mod } 10^9+7 and 0 \leq x < 10^9+7.