You are given a positive integer NN and a set of six-tuples. We define the value of a six-tuple (lx,rx,ly,ry,lz,rz)(lx,rx,ly,ry,lz,rz) is ∑lx≤x≤rx,ly≤y≤ry,lz≤z≤rz,x⊕y⊕z∑lx≤x≤rx,ly≤y≤ry,lz≤z≤rz,x⊕y⊕z. In the beginning, the set has only an element (0,N−1,0,N−1,0,N−1)(0,N−1,0,N−1,0,N−1). You can do the following steps repeatedly until the size of SSequals to N3N3:
∙∙ Pick a six-tuple (lx,rx,ly,ry,lz,rz)(lx<rxorly<ryorlz<rz)(lx,rx,ly,ry,lz,rz)(lx<rxorly<ryorlz<rz) from the set.
∙∙ You can choose one element of {x,y,z}{x,y,z}.
∘ ∘ Assuming you chose xx, it must be satisfied that lx<rxlx<rx. Then you should pick an integer t∈[lx,rx)t∈[lx,rx), erase (lx,rx,ly,ry,lz,rz)(lx,rx,ly,ry,lz,rz) from the set, add
(lx,t,ly,ry,lz,rz)(lx,t,ly,ry,lz,rz) and (t+1,rx,ly,ry,lz,rz)(t+1,rx,ly,ry,lz,rz) into the set, and you will get the product of values of these two new six-tuples.
∘ ∘ Assuming you chose yy, it must be satisfied that ly<ryly<ry. Then you should pick an integer t∈[ly,ry)t∈[ly,ry), erase (lx,rx,ly,ry,lz,rz)(lx,rx,ly,ry,lz,rz) from the set, add
(lx,rx,ly,t,lz,rz)(lx,rx,ly,t,lz,rz) and (lx,rx,t+1,ry,lz,rz)(lx,rx,t+1,ry,lz,rz) into the set, and you will get the product of values of these two new six-tuples.
∘ ∘ Assuming you chose zz, it must be satisfied that lz<rzlz<rz. Then you should pick an integer t∈[lz,rz)t∈[lz,rz), erase (lx,rx,ly,ry,lz,rz)(lx,rx,ly,ry,lz,rz) from the set, add
(lx,rx,ly,ry,lz,t)(lx,rx,ly,ry,lz,t) and (lx,rx,ly,ry,t+1,rz)(lx,rx,ly,ry,t+1,rz) into the set, and you will get the product of values of these two new six-tuples.
Maximize the sum of values you got and output it modulo 998244353998244353.
Note that ⊕⊕ means exclusive or, for more details refer tohttps://en.wikipedia.org/wiki/Exclusive_or.