Karev really enjoys simple sequences of at most K numbers. A simple sequence oflength K is a sequence formed by the numbers from 0 to K-1 in this order. For example,simple sequences are {0}, {0,1,2,3}, {0,1,2,3,4,5,6}, while the sequences {1}, {0,1,3,2}, {0,1,3}– are not.Since Karev’s birthday is approaching, Polly would like to buy for him a few simplesequences and combine them into an interesting sequence. An interesting sequence is asequence formed by concatenating a few simple sequences, each with length at most K. Forexample, let K=3. Then {0,1,2,0}, {0,1,0,1}, {0,0,0} and {0,1,2} are interesting sequences, but{0,1,2,3}, {0,1,1} and {0,0,2} are not.Since Polly can choose many sequences, she is wondering which one to pick. Now sheis curious how many choices she really has. Karev is a very good friend of Polly so she mightdecide to buy a really huge present for him.