An airline runs flights between several cities of the world. Ev- ery flight connects two cities. A millionaire wants to travel from Dharwad to Luxembourg by changing at most k − 1 flights. Being a millionaire with plenty of time and money, he does not mind revisiting the same city multiple times, or even taking the same flight multiple times in his quest. Can you help the millionaire by describing how to compute the number of ways he can make his journey? How many steps does your procedure take if there are n cities and he can change flights at most k − 1 times. You can assume that the procedure can add or multiply two numbers in a single operation.