Derangement count

A derangement of n distinct items is a permutation in which no item appears in its original position. Given n (0 <= n <= 10^6) and a modulus mod (>= 2), return the number of derangements of n items, modulo mod. By convention there is exactly one derangement of 0 items (the empty arrangement) and zero derangements of 1 item. For example, 3 items have 2 derangements.