{"problem":{"name":"11","description":{"content":"You are given an integer sequence of length $n+1$, $a_1,a_2,...,a_{n+1}$, which consists of the $n$ integers $1,...,n$. It is known that each of the $n$ integers $1,...,n$ appears at least once in thi","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc077_b"},"statements":[{"statement_type":"Markdown","content":"You are given an integer sequence of length $n+1$, $a_1,a_2,...,a_{n+1}$, which consists of the $n$ integers $1,...,n$. It is known that each of the $n$ integers $1,...,n$ appears at least once in this sequence.\nFor each integer $k=1,...,n+1$, find the number of the different subsequences (not necessarily contiguous) of the given sequence with length $k$, modulo $10^9+7$.\n\n## Constraints\n\n*   $1 \\leq n \\leq 10^5$\n*   $1 \\leq a_i \\leq n$\n*   Each of the integers $1,...,n$ appears in the sequence.\n*   $n$ and $a_i$ are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$n$\n$a_1$ $a_2$ ... $a_{n+1}$\n\n[samples]\n\n## Notes\n\n*   If the contents of two subsequences are the same, they are not separately counted even if they originate from different positions in the original sequence.\n    \n*   A subsequence of a sequence $a$ with length $k$ is a sequence obtained by selecting $k$ of the elements of $a$ and arranging them without changing their relative order. For example, the sequences $1,3,5$ and $1,2,3$ are subsequences of $1,2,3,4,5$, while $3,1,2$ and $1,10,100$ are not.","is_translate":false,"language":"English"}],"meta":{"iden":"arc077_b","tags":[],"sample_group":[["3\n1 2 1 3","3\n5\n4\n1\n\nThere are three subsequences with length $1$: $1$ and $2$ and $3$.\nThere are five subsequences with length $2$: $1,1$ and $1,2$ and $1,3$ and $2,1$ and $2,3$.\nThere are four subsequences with length $3$: $1,1,3$ and $1,2,1$ and $1,2,3$ and $2,1,3$.\nThere is one subsequence with length $4$: $1,2,1,3$."],["1\n1 1","1\n1\n\nThere is one subsequence with length $1$: $1$.\nThere is one subsequence with length $2$: $1,1$."],["32\n29 19 7 10 26 32 27 4 11 20 2 8 16 23 5 14 6 12 17 22 18 30 28 24 15 1 25 3 13 21 19 31 9","32\n525\n5453\n40919\n237336\n1107568\n4272048\n13884156\n38567100\n92561040\n193536720\n354817320\n573166440\n818809200\n37158313\n166803103\n166803103\n37158313\n818809200\n573166440\n354817320\n193536720\n92561040\n38567100\n13884156\n4272048\n1107568\n237336\n40920\n5456\n528\n33\n1\n\nBe sure to print the numbers modulo $10^9+7$."]],"created_at":"2026-03-03 11:01:14"}}