ADADUNG - Ada and Manure
As you might know Ada the Ladybug is farmer. Last year, she sowed N distinct types of grain to N distinct places. This year she wants to seed the same types of grain again, yet there is a little problem: each type of grain needs special kind of manure, yet fertilizing soil with same kind of manure in consecutive years might destroy it.
Now she is asking you to count the number of ways, to seed N types of grain to N places in such way that no type of grain will be in its original place. Since this number might be pretty big, print it modulo 109+7.
The first line contains 1 ≤ T ≤ 105 , number of test-cases.
Each of following T lines contains 1 ≤ N ≤ 107, number of types/places.
For each test case, print the number of possibilities for given number of types/places modulo 1000000007.
5 2 3 10 100 666
1 2 1334961 944828409 769756093
Ez derangements question
calculated for first 5 numbers and looked for a pattern & bingo AC :D
I tried precomputation using derangement formula but it gave me tle..:-(