2015 AIME II Problem 10

Call a permutation a_1, a_2, \ldots, a_n of the integers 1, 2, \ldots, n *quasi-increasing* if a_k \leq a_{k+1} + 2 for each 1 \leq k \leq n-1. For example, 53421 and 14253 are quasi-increasing permutations of the integers 1, 2, 3, 4, 5, but 45123 is not. Find the number of quasi-increasing permutations of the integers 1, 2, \ldots, 7.

Leading zeroes must be inputted, so if your answer is 34, then input 034

Full credit goes to MAA for authoring these problems. These problems were taken on the AOPS website.