#P17701. [2026年江苏省队集训]升

[2026年江苏省队集训]升

题面描述

给定长为 nn 的三个非负整数序列 {ai}\{a_i\},{li}\{l_i\} 和 {ri}\{r_i\},求出满足下列条件的非负整数序列 {bi}\{b_i\} 的个数:

  • 序列 {bi}\{b_i\} 的长度为 nn;
  • bi∈[li,ri]b_i\in [l_i,r_i];
  • bi and ai=aib_i \text{ and }a_i=a_i;
  • 序列 {bi}\{b_i\} 单调递增。

其中 and\text{and} 表示二进制按位与运算。答案对 998 244 353998\,244\,353 取模。

输入格式

输入的第一行包含一个正整数 nn。

输入的第二行包含 nn 个非负整数,表示序列 {ai}\{a_i\}。

输入的第三行包含 nn 个非负整数,表示序列 {li}\{l_i\}。

输入的第四行包含 nn 个非负整数,表示序列 {ri}\{r_i\}。

输出格式

输出答案对 998 244 353998\,244\,353 取模后的结果。

样例输入与输出

3
0 0 0
0 0 0
10 10 10
165

数据范围与子任务

对于所有数据,满足 1≤n≤1001\leq n\leq 100,0≤ai,li,ri<2600\leq a_i,l_i,r_i<2^{60}。

子任务编号 子任务分值 n≤n\leq aia_i ri<r_i<
11 88 1010 <260<2^{60} 252^5
22 1212 100100 2172^{17}
33 88 77 2602^{60}
44 1212 1010
55 2020
66 100100 =0=0
77 1616 <28<2^8
88 2020 <260<2^{60}