Gift Exchange

Every participant in an event prepared exactly one gift.

After the event, the gifts will be handed out among the participants. Each participant must receive exactly one gift, and nobody may receive the gift they prepared.

Find the number of ways to hand out the gifts while satisfying these conditions.

The first line contains the number of participants N. (1 ≤ N ≤ 1,000,000)

Print the number of valid gift assignments modulo 1,000,000,000 on the first line.