No tag edit access

E. Positions in Permutations

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPermutation *p* is an ordered set of integers *p*_{1}, *p*_{2}, ..., *p*_{n}, consisting of *n* distinct positive integers, each of them doesn't exceed *n*. We'll denote the *i*-th element of permutation *p* as *p*_{i}. We'll call number *n* the size or the length of permutation *p*_{1}, *p*_{2}, ..., *p*_{n}.

We'll call position *i* (1 ≤ *i* ≤ *n*) in permutation *p*_{1}, *p*_{2}, ..., *p*_{n} good, if |*p*[*i*] - *i*| = 1. Count the number of permutations of size *n* with exactly *k* good positions. Print the answer modulo 1000000007 (10^{9} + 7).

Input

The single line contains two space-separated integers *n* and *k* (1 ≤ *n* ≤ 1000, 0 ≤ *k* ≤ *n*).

Output

Print the number of permutations of length *n* with exactly *k* good positions modulo 1000000007 (10^{9} + 7).

Examples

Input

1 0

Output

1

Input

2 1

Output

0

Input

3 2

Output

4

Input

4 1

Output

6

Input

7 4

Output

328

Note

The only permutation of size 1 has 0 good positions.

Permutation (1, 2) has 0 good positions, and permutation (2, 1) has 2 positions.

Permutations of size 3:

- (1, 2, 3) — 0 positions
- — 2 positions
- — 2 positions
- — 2 positions
- — 2 positions
- (3, 2, 1) — 0 positions

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/28/2018 00:38:16 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|