3991. 选择题

在 2011 年 NOIP 提高组的初赛题中，Cuber QQ 遇到了这个选择题：

公元 1956 年，肖克利、巴丁和布拉顿共同获得了：

• A. 诺贝尔物理学奖
• B. 约翰·冯·诺依曼奖
• C. 图灵奖
• D. 高德纳奖

冯·诺依曼奖是 1990 年成立的，图灵奖是 1966 年设立的，高德纳奖是 1996 年设立的。因此答案选 A。

如今 Cuber QQ 想要出很多道这样的题。在出题之前，他希望你帮他预估一下工作量。

Cuber QQ 会给你 $n$ 个著名历史人物的资料。第 $i$ 个历史人物的资料如下（假设他/她的名字是 $i$ 神）：

• 出生年份为 $a_i$。
• 以他的名字命名的奖项的设立年份为 $b_i$（$a_i<b_i$）。即，$b_i$ 年是第一届$i$ 神奖。该奖项为一年一届。

此外，Cuber QQ 还会给你 $m$ 个有意义的年份，记作 $d_1,\dots ,d_m$。

一道选择题形如：

公元 $d_t$（$1\le t\le m$） 年，第 $e$（$1\le e\le n$） 个著名历史人物获得了：

• A. $A$ 神奖
• B. $B$ 神奖
• C. $C$ 神奖
• D. $D$ 神奖

我们用元组 $(t,e,A,B,C,D)$ 表示选择题。

Cuber QQ 的出题有一些限制：

• $A<B<C<D$，即四个选项互不相同；
• $a_e<d_t$，即历史人物必须在颁奖时间前出生；
• $x\in A,B,C,D$ 中有且仅有一个选项满足： $b_x\le d_t$。即颁奖时间在奖项成立时间之后。

Cuber QQ 认为两个题是不同的当且仅当有序元组 $(t,e,A,B,C,D)$ 存在一位不同。

Cuber QQ 想知道一共能出多少道不一样的选择题，对 $114514$ 取模后输出。