{"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 permutation in the lexicographical order.\nMr. Takahashi wanted to look up a certain permutation of length $N$ in this dictionary, but he forgot some part of it.\nHis 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$.\nHe 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$.\n\n## Constraints\n\n*   $1 ≤ N ≤ 500000$\n*   $0 ≤ P_i ≤ N$\n*   $P_i ≠ P_j$ if $i ≠ j$ ($1 ≤ i, j ≤ N$), $P_i ≠ 0$ and $P_j ≠ 0$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$P_1$ $P_2$ $...$ $P_N$\n\n## Partial Score\n\n*   In test cases worth $500$ points, $1 ≤ N ≤ 3000$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"codefestival_2016_qualC_e","tags":[],"sample_group":[["4\n0 2 3 0","23\n\nThe 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$."],["3\n0 0 0","21\n\nSince all permutations of length $3$ are possible, the answer is $1 + 2 + 3 + 4 + 5 + 6 = 21$."],["5\n1 2 3 5 4","2\n\nMr. Takahashi remembered all the elements of the permutation."],["1\n0","1\n\nThe dictionary consists of one page."],["10\n0 3 0 0 1 0 4 0 0 0","953330050"]],"created_at":"2026-03-03 11:01:14"}}