For any integer n ≥ 1, a permutation a1, a2, . . . , an of the set {1, 2, . . . , n} is called awesome, if the following condition holds:• For every i with 1 ≤ i ≤ n, the element ai in the permutation belongs to the set{i - 1, i, i + 1}.For example, for n = 5, the permutation 2, 1, 3, 5, 4 is awesome, whereas 2, 1, 5, 3, 4 is not anawesome permutation.Let Pn denote the number of awesome permutations of the set {1, 2, . . . , n}.• Determine P1, P2, and P3.• Determine the value of Pn, i.e., express Pn in terms of numbers that we have seen inclass. Justify your answer.Hint: Derive a recurrence relation. What are the possible values for the last element an in an awesome permutation?