Chef and Trip

Chef and his friend Chefu decided to go on a trip. The trip takes place over the next $N$ days (numbered 1 through $N$). There are $K$ different places Chef and Chefu could visit (numbered 1 through $K$). They have written a sequence $A_1, A_2, \ldots, A_N$ which denotes the plan of the trip during these $N$ days; however, the plan is not completed yet. For each valid $i$, they want to visit the p