{"problem":{"name":"RGB Coloring","description":{"content":"Takahashi has a tower which is divided into $N$ layers. Initially, all the layers are uncolored. Takahashi is going to paint some of the layers in red, green or blue to make a beautiful tower. He defi","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc025_b"},"statements":[{"statement_type":"Markdown","content":"Takahashi has a tower which is divided into $N$ layers. Initially, all the layers are uncolored. Takahashi is going to paint some of the layers in red, green or blue to make a beautiful tower. He defines the _beauty of the tower_ as follows:\n\n*   The beauty of the tower is the sum of the scores of the $N$ layers, where the score of a layer is $A$ if the layer is painted red, $A+B$ if the layer is painted green, $B$ if the layer is painted blue, and $0$ if the layer is uncolored.\n\nHere, $A$ and $B$ are positive integer constants given beforehand. Also note that a layer may not be painted in two or more colors.\nTakahashi is planning to paint the tower so that the beauty of the tower becomes exactly $K$. How many such ways are there to paint the tower? Find the count modulo $998244353$. Two ways to paint the tower are considered different when there exists a layer that is painted in different colors, or a layer that is painted in some color in one of the ways and not in the other.\n\n## Constraints\n\n*   $1 ≤ N ≤ 3×10^5$\n*   $1 ≤ A,B ≤ 3×10^5$\n*   $0 ≤ K ≤ 18×10^{10}$\n*   All values in the input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $A$ $B$ $K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc025_b","tags":[],"sample_group":[["4 1 2 5","40\n\nIn this case, a red layer worth $1$ points, a green layer worth $3$ points and the blue layer worth $2$ points. The beauty of the tower is $5$ when we have one of the following sets of painted layers:\n\n*   $1$ green, $1$ blue\n*   $1$ red, $2$ blues\n*   $2$ reds, $1$ green\n*   $3$ reds, $1$ blue\n\nThe total number of the ways to produce them is $40$."],["2 5 6 0","1\n\nThe beauty of the tower is $0$ only when all the layers are uncolored. Thus, the answer is $1$."],["90081 33447 90629 6391049189","577742975"]],"created_at":"2026-03-03 11:01:14"}}