Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tags yet

No tag edit access

E. Sorting Permutations

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputWe are given a permutation sequence *a*_{1}, *a*_{2}, ..., *a*_{n} of numbers from 1 to *n*. Let's assume that in one second, we can choose some disjoint pairs (*u*_{1}, *v*_{1}), (*u*_{2}, *v*_{2}), ..., (*u*_{k}, *v*_{k}) and swap all *a*_{ui} and *a*_{vi} for every *i* at the same time (1 ≤ *u*_{i} < *v*_{i} ≤ *n*). The pairs are disjoint if every *u*_{i} and *v*_{j} are different from each other.

We want to sort the sequence completely in increasing order as fast as possible. Given the initial permutation, calculate the number of ways to achieve this. Two ways are different if and only if there is a time *t*, such that the set of pairs used for swapping at that time are different as sets (so ordering of pairs doesn't matter). If the given permutation is already sorted, it takes no time to sort, so the number of ways to sort it is 1.

To make the problem more interesting, we have *k* holes inside the permutation. So exactly *k* numbers of *a*_{1}, *a*_{2}, ..., *a*_{n} are not yet determined. For every possibility of filling the holes, calculate the number of ways, and print the total sum of these values modulo 1000000007 (10^{9} + 7).

Input

The first line contains two integers *n* (1 ≤ *n* ≤ 10^{5}) and *k* (0 ≤ *k* ≤ 12). The second line contains the permutation sequence *a*_{1}, ..., *a*_{n} (0 ≤ *a*_{i} ≤ *n*). If a number is not yet determined, it is denoted as 0. There are exactly *k* zeroes. All the numbers *a*_{i} that aren't equal to zero are distinct.

Output

Print the total sum of the number of ways modulo 1000000007 (10^{9} + 7).

Examples

Input

5 0

1 5 2 4 3

Output

6

Input

5 2

1 0 2 4 0

Output

7

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 10:31:00 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|