2019 AIME II Problem 2

Lily pads 1,2,3, \ldots lie in a row on a pond. A frog makes a sequence of jumps starting on pad 1. From any pad k the frog jumps to either pad k+1 or pad k+2 chosen randomly and independently with probability \frac{1}{2}. The probability that the frog visits pad 7 is \frac{p}{q}, where p and q are relatively prime positive integers. Find p+q.