{"problem":{"name":"Nim Counting","description":{"content":"Given are positive integers $N$, $K$, and a sequence of $K$ integers $(A_1, A_2, \\ldots, A_K)$. Takahashi and Aoki will play a game with stones. Initially, there are some heaps of stones, each of whic","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc212_h"},"statements":[{"statement_type":"Markdown","content":"Given are positive integers $N$, $K$, and a sequence of $K$ integers $(A_1, A_2, \\ldots, A_K)$.\nTakahashi and Aoki will play a game with stones. Initially, there are some heaps of stones, each of which contains one or more stones. The players take turns doing the following operation, with Takahashi going first.\n\n*   Choose a heap with one or more stones remaining. Remove any number of stones between $1$ and $X$ (inclusive) from that heap, where $X$ is the number of stones remaining.\n\nThe player who first gets unable to do the operation loses.\nNow, consider the initial arrangements of stones satisfying the following.\n\n*   $1\\leq M\\leq N$ holds, where $M$ is the number of heaps of stones.\n*   The number of stones in each heap is one of the following: $A_1, A_2, \\ldots, A_K$.\n\nAssuming that the heaps are ordered, there are $K+K^2+\\cdots +K^N$ such initial arrangements of stones. Among them, find the number, modulo $998244353$, of arrangements that lead to Takahashi's win, assuming that both players play optimally.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2\\times 10^5$\n*   $1 \\leq K < 2^{16}$\n*   $1 \\leq A_i < 2^{16}$\n*   All $A_i$ are distinct.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n$A_1$ $A_2$ $\\ldots$ $A_K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc212_h","tags":[],"sample_group":[["2 2\n1 2","4\n\nThere are six possible initial arrangements of stones: $(1)$, $(2)$, $(1,1)$, $(1,2)$, $(2,1)$, and $(2,2)$.  \nTakahashi has a winning strategy for four of them: $(1)$, $(2)$, $(1,2)$, and $(2,1)$, and Aoki has a winning strategy for the other two. Thus, we should print $4$."],["100 3\n3 5 7","112184936\n\nBe sure to find the count modulo $998244353$."]],"created_at":"2026-03-03 11:01:13"}}