Let us assume that Alice is given the task to calculate the number of lucky sequences of length \(3\). She will hire Bob and ask him to calculate the number of sequences of length \(3\) that start with number \(1\). Then she will hire Carol to calculate the number of lucky sequences of length \(3\) that start with \(2\). Alice then hires David to calculate the number of lucky sequences of length \(3\) that start with \(3\). Once Bob, Carol, and David return their answers, then Alice adds up the numbers and starts celebrating because she completed her job.

Let us now look at Bob's task. Bob needs to calculate the number of lucky sequences of length \(3\) that start with \(1\). Bob observes that the next number can be \(1\) or \(2\). Bob hires Ellen and gives her the task to calculate the number of lucky sequences of length \(2\) that starts with \(1\). Bob hires Frank to count the number of lucky sequences of length \(2\) that start with \(1\). Once Bob receives the answers from Ellen and Frank, he adds them up and returns the result to Alice.

Carol needs to count the lucky sequences of length \(3\) that start with \(2\). She observes that the next term can be \(1\), \(2\), or \(3\). Carol hires Gina with the task to count lucky sequences of length \(2\) that start with \(1\). Then she hires Henry to count the lucky sequences of length \(2\) that start with \(2\). Finally, Carol hires Ina to count the lucky sequences of length \(2\) that start with \(3\). After Gina, Henry, and Ina complete their task and send their answers to Carol, Carol is able to add the numbers and send the answer to Alice.

David does a very similar job to Carol.

Now let us look at Ellen's job. She is the one hired by Bob. Ellen's task is to count the lucky sequences of length \(2\) that start with \(1\). She knows that the next term can be either \(1\) or \(2\). Ellen then hires John to count lucky sequences of length \(1\) that start with \(1\). Ellen also hires Kevin to count the lucky sequences of length \(1\) that start with \(2\).

John and Kevin will not be able to hire anyone. Their tasks are possible to manage. John needs to count the number of sequences whose length is \(1\) and that start with \(1\). There is only one such sequence. Similarly, Kevin needs to count the sequences that have length \(1\) and start with \(2\). There is only one such sequence.

It turns out that every person who was hiring the employees is always submitting a request of the same form: "Count the lucky sequences of length \(l\) that start with \(s\)."

This is a perfect opportunity to create the function `luckySequences`

with two arguments: `len`

and `start`

. The full implementation of the code is given below

#include<iostream>
long luckySequences(long len, long start){
long result;
if(len < 2){
result = 1;
}
else{
if(start==1){
result=luckySequences(len-1,1)+luckySequences(len-1,2);
}
else{
result=luckySequences(len-1,1)+luckySequences(len-1,2)+luckySequences(len-1,3);
}
}
return result;
}
int main(){
int n;
std::cin >> n;
std::cout << luckySequences(n,1)+luckySequences(n,2)+luckySequences(n,3);
std::cout << "\n";
return 0;
}