As you may already know, Eddy likes to walk around. Especially, he likes to walk in a number line called "Infinite line". Actually, it's exactly a line with infinite length!Eddy is at number 0 and starts to walk around. Since Eddy is a little drunk, he will not walk in a fixed length. Instead, he will independently uniformly randomly walk in an integer length between 1 and K. That is, he will walk for 1 unit of length in a probability of. . If he currently stands on number i and walk for j unit of length, he will end up on number i+j.Since Eddy is drunk, he will walk around infinitely. You, somehow, notice this weird thing and start wondering whether will Eddy ever step on the number N. However, you don't want to wait for such stupid thing. You would like to compute the probability that Eddy would ever step on number N.
As you may already know, Eddy likes to walk around. Especially, he likes to walk in a number line called "Infinite line". Actually, it's exactly a line with infinite length! Eddy is at number 0 and starts to walk around. Since Eddy is a little drunk(just finished his work, make sense), he will not walk in a fixed length. Instead, he will independently uniformly randomly walk in an integer length between 1 and K. That is, he will walk for 1 unit of length in a probability of frac{1}{K} K 1 , 2 units in frac{1}{K} K 1 , cdots ⋯, K units in frac{1}{K} K 1 . If he currently stands on number i and walk for j unit of length, he will end up on number i+j. Since Eddy is drunk, he will walk around infinitely. You, somehow, notice this weird thing and start wondering whether will Eddy ever step on the number N. However, you don't want to wait for such stupid thing. You would like to compute the probability that Eddy would ever step on number N.
