Sauron's Army


After the last war of the five armies, Sauron wants to make his army more powerful. For that he has found an error that needs to be corrected, the soldiers are tired of seeing the same preceding soldier in the line. Then he needs to know in how many ways he can arrange each line so that no soldier sees the same preceding soldier of the last war. Given the line of N soldiers compute the amount of arrangements that meet the above rules.


The only line of input contains an integer N (1 ≤ N ≤ 500).


Print a line with the amount of arrangements mod 109 + 7 (1000000007).

Example input:
Example output:

For the sample input the possibles permutations are [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. If the first permutation was used in the last war then the possible permutations that meet the rules are [1,3,2], [2,1,3], [3,2,1].

Time and memory limit:

  • 1s
  • 64MB

Problem source: Caribbean Online Judge