P4229 某位歌姬的故事

IA 是一名会唱歌的女孩子。 IOI2018 就要来了，IA 决定给参赛选手们写一首歌，以表达美好的祝愿。这首歌一共有 $n$ 个音符，第 $i$ 个音符的音高为 $h_i$​​。IA 的音域是 $A$，她只能唱出 $1\sim A$ 中的正整数音高。因此 $1\le h_i\le A$。 在写歌之前，IA 需要确定下这首歌的结构，于是她写下了 $Q$ 条限制，其中第 $i$ 条为：编号在 $l_i$ 到 $r_i$ 之间的音符的最高音高为 $m_i$。在确定了结构之后，她就可以开始写歌了。不过她还是想知道，一共有多少种可能的歌曲满足她的所有限制？她听说你还有 9 个月就要去 IOI 了，于是希望你帮她计算一下这个值。

无

无

**样例1解释** 以下是三种可能的歌曲：$(3,1,2),(3,2,1),(3,2,2)$。