Brachylog, 12 bytes
{^a₀.&b~b^}ᶜ
Explanation
{^a₀.&b~b^}ᶜ
{ }ᶜ Count the number of ways the following can succeed:
a₀ A prefix of
^ the first {input} to the power of the second {input}
.& produces the same output with the same input as
~b any number
^ to the power of
b all inputs but the lastfirst (i.e. the second input)