P r o b l e m \mathrm{Problem} Problem
题目描述
你有三个整数 n , k , m n, k, m n,k,m 以及 m m m 个限制 ( l 1 , r 1 , x 1 ) , ( l 2 , r 2 , x 2 ) , … , ( l m , r m , x m ) (l_1, r_1, x_1), (l_2, r_2, x_2), \ldots, (l_m, r_m, x_m) (l1?,r1?,x1?),(l2?,r2?,x2?),…,(lm?,rm?,xm?)。
计算满足下列条件的，长度为 n n n 的序列 a a a 的个数：
- 对于每个 1 ≤ i ≤ n 1 \le i \le n 1≤i≤n， 0 ≤ a i < 2 k 0 \le a_i \lt 2 ^ k 0≤ai?<2k。
- 对于每个 1 ≤ i ≤ m 1 \le i \le m 1≤i≤m，数字的按位与 a [ l i ] and a [ l i + 1 ] and … and a [ r i ] = x i a[l_i] \text{ and } a_[l_i + 1] \text{ and } \ldots \text{ and } a