First of all, let M(i, j) be equal to 1, if L(i, j) > 0, otherwise 0. It's clear that

Now find . It's almost upper-triangular matrix, so one can see that each sequence

adds $(-1)^k$ to . It's easy to calculate dp[parity][n] corresponding for the number of such sequences ending with n and having length with parity parity.

For each n let F_n be the number of permutations of {1, 2, . . . , n} with the required property; call them good. For n = 1, 2, 3 every permutation is good, so F₁ = 1, F₂ = 2, F₃ = 6.

Take an n > 3 and consider any good permutation (a₁, a₂, . . . , a_n) of {1, 2, . . . , n}. Then n − 1 must be a divisor of the number

2(a₁ + a₂ + · · · + a_n−1)
= 2(1 + 2 + · · · + n − a_n )
= n(n + 1) − 2a_n = (n + 2)(n − 1) + (2 − 2a_n ).

So 2a_n − 2 must be divisible by n − 1, hence equal to 0 or n − 1 or 2n − 2. This means that a_n = 1 or a_n = (n + 1)/2 or a_n = n. Suppose that a_n = (n + 1)/2. Since the permutation is good, taking k = n−2 we get that n-2 has to be a divisor of

2(a₁ + a₂ + · · · + a_n−2) = 2(1 + 2 + · · · + n) − a_n − a_n−1
= n(n + 1) − (n + 1) − 2a_n−1 = (n + 2)(n − 2) + (3 − 2a_n−1).

So 2a_n−1 − 3 should be divisible by n − 2, hence equal to 0 or n − 2 or 2n − 4. Obviously 0 and 2n − 4 are excluded because 2a_n−1 − 3 is odd. The remaining possibility (2a_n−1 − 3 = n − 2) leads to a_n−1 = (n + 1)/2 = a_n, which also cannot hold. This eliminates (n + 1)/2 as a possible value of a_n. Consequently a_n = 1 or a_n = n.

If a_n = n then (a₁, a₂, . . . , a_n−1) is a good permutation of {1, 2, . . . , n−1}. There are F_n−1 such permutations. Attaching n to any one of them at the end creates a good permutation of {1, 2, . . . , n}.

If a_n = 1 then (a₁−1, a₂−1, . . . , a_n−1−1) is a permutation of {1, 2, . . . , n−1}. It is also good because the number 2(a₁−1) + · · · + (a_k−1) = 2(a₁ + · · · + a_k) − 2k is divisible by k, for any k ≤ n − 1. And again, any one of the F_n−1 good permutations (b₁, b₂, . . . , b_n−1) of {1, 2, . . . , n−1} gives rise to a good permutation of {1, 2, . . . , n} whose last term is 1, namely (b₁+1, b₂+1, . . . , b_n−1+1, 1).

The bijective correspondences established in both cases show that there are F_n−1 good permutations of {1, 2, . . . , n} with the last term 1 and also F_n−1 good permutations of {1, 2, . . . , n} with the last term n. Hence follows the recurrence F_n = 2F_n−1. With the base value F₃ = 6 this gives the outcome formula F_n = 3 * 2ⁿ⁻² for n ≥ 3.