Fixed Point Permutations

Given two integers n and m, count the number of permutations a of the numbers from 1 to n such that exactly m positions i satisfy a_i = i (i.e. fixed points).

The answer should be computed modulo \(10^9+7\).

A useful formula is:

\[ \text{Answer} = \binom{n}{m} \cdot D(n-m) \mod (10^9+7), \]

where \(D(k)\) denotes the number of derangements (permutations with no fixed points) of \(k\) elements. It can be computed using the recurrence:

\[ D(0)=1,\quad D(1)=0,\quad D(k)=(k-1)(D(k-1)+D(k-2)) \quad (k \ge 2). \]

inputFormat

The input consists of a single line containing two integers n and m separated by a space.

\(1 \leq n \leq 10^5\), \(0 \leq m \leq n\).

outputFormat

Output a single integer -- the number of valid permutations modulo \(10^9+7\).

sample

3 1

3