{"problem":{"name":"Again ABC String","description":{"content":"Consider strings of length $N$ consisting of `A`, `B`, and `C`. Among them, find the number of strings that satisfy the following condition, modulo $2$: *   Let $S_i$ be the string formed by the firs","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc147_f"},"statements":[{"statement_type":"Markdown","content":"Consider strings of length $N$ consisting of `A`, `B`, and `C`. Among them, find the number of strings that satisfy the following condition, modulo $2$:\n\n*   Let $S_i$ be the string formed by the first $i$ characters of $S$. Also let $A_i$, $B_i$, and $C_i$ be the numbers of `A`'s, `B`'s, and `C`'s in $S_i$, respectively. For all $i$ such that $1 \\le i \\le N$, the following holds:\n    *   $A_i-B_i \\le X$\n    *   $B_i-C_i \\le Y$\n    *   $C_i-A_i \\le Z$\n\nYou have $T$ test cases to solve.\n\n## Constraints\n\n*   $1 \\le T \\le 10$\n*   $1 \\le N \\le 10^9$\n*   $0 \\le X,Y,Z \\le 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is in the following format:\n\n$N$ $X$ $Y$ $Z$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc147_f","tags":[],"sample_group":[["1\n3 2 1 0","0\n\n$8$ strings satisfy the condition: `AAB`,`AAC`,`ABA`,`ABC`,`ACA`,`ACB`,`BAA`,`BAC`. Therefore the answer is $0$."],["10\n1 22 9 92\n14 7 74 39\n23 50 8 6\n93 40 9 60\n68 8 47 64\n11 68 18 24\n3 26 54 8\n46 17 90 86\n86 76 45 55\n80 68 79 62","1\n0\n0\n0\n1\n1\n1\n0\n1\n0"]],"created_at":"2026-03-03 11:01:13"}}