Encyclopedia of Permutations

AtCoder

IDcodefestival_2016_qualC_e

Time2000ms

Memory256MB

Difficulty—

One day Mr. Takahashi picked up a dictionary containing all of the $N$! permutations of integers $1$ through $N$. The dictionary has $N$! pages, and page $i$ ($1 ≤ i ≤ N!$) contains the $i$\-th permutation in the lexicographical order. Mr. Takahashi wanted to look up a certain permutation of length $N$ in this dictionary, but he forgot some part of it. His memory of the permutation is described by a sequence $P_1, P_2, ..., P_N$. If $P_i = 0$, it means that he forgot the $i$\-th element of the permutation; otherwise, it means that he remembered the $i$\-th element of the permutation and it is $P_i$. He decided to look up all the possible permutations in the dictionary. Compute the sum of the page numbers of the pages he has to check, modulo $10^9 + 7$. ## Constraints * $1 ≤ N ≤ 500000$ * $0 ≤ P_i ≤ N$ * $P_i ≠ P_j$ if $i ≠ j$ ($1 ≤ i, j ≤ N$), $P_i ≠ 0$ and $P_j ≠ 0$. ## Input The input is given from Standard Input in the following format: $N$ $P_1$ $P_2$ $...$ $P_N$ ## Partial Score * In test cases worth $500$ points, $1 ≤ N ≤ 3000$. [samples]

Samples

Input #1

4
0 2 3 0

Output #1

23

The possible permutations are \[$1$, $2$, $3$, $4$\] and \[$4$, $2$, $3$, $1$\]. Since the former is on page $1$ and the latter is on page $22$, the answer is $23$.

Input #2

3
0 0 0

Output #2

21

Since all permutations of length $3$ are possible, the answer is $1 + 2 + 3 + 4 + 5 + 6 = 21$.

Input #3

5
1 2 3 5 4

Output #3

2

Mr. Takahashi remembered all the elements of the permutation.

Input #4

1
0

Output #4

1

The dictionary consists of one page.

Input #5

10
0 3 0 0 1 0 4 0 0 0

Output #5

953330050

API Response (JSON)

{
  "problem": {
    "name": "Encyclopedia of Permutations",
    "description": {
      "content": "One day Mr. Takahashi picked up a dictionary containing all of the $N$! permutations of integers $1$ through $N$. The dictionary has $N$! pages, and page $i$ ($1 ≤ i ≤ N!$) contains the $i$\\-th permut",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "codefestival_2016_qualC_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "One day Mr. Takahashi picked up a dictionary containing all of the $N$! permutations of integers $1$ through $N$. The dictionary has $N$! pages, and page $i$ ($1 ≤ i ≤ N!$) contains the $i$\\-th permut...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments