U323199 空灵之魂

影魔喜欢空灵的灵魂，他准备收集 n 个人的灵魂，然而灵魂充满了意志力，第 i 个灵魂的意志力为 di 他拥有 D 天时间来削弱灵魂们的意志，第 i 天他可以削弱所有灵魂ai 点意志力或者不操作，当一个灵魂的意志力 ≤ 0 的时候，其将成为影魔的俘虏。 然而灵魂的意志均会得到强化，在第 i 天开始时，编号为ci 的灵魂如果未被俘虏，则其会回复 ti 点意志力(注意灵魂的意志力没有上限) **需要注意的是，每天只有一个灵魂会回复意志力，同一个灵魂不会回复意志力多次。** 影魔希望你求出有多少种削弱灵魂意志的方案可以俘虏所有灵魂，注意，两个方案不同，当且仅当，某一天其中一个进行了操作但是另一个没有，不关乎于其何时俘虏所有灵魂。由于答案确实很大，所以你只需要输出答案对于 1e9+ 7 取模 的结果

第一行两个正整数表示 D 和 n 。 接下来一行，共 n 个正整数，表示第 i 个灵魂的初始意志力di 接下来 D 行，每行三个正整数依次表示 ci , ai , ti，保证 ci 互不相等

共一行一个正整数，表示可以俘虏所有灵魂的方案的方案数对于 1e9+ 7 取模的结果

#### 样例解释 一共有 8 种可能的序列，其中有 2 种操作序列合法。 下面将列举这 8 种可能的序列： 1.完全不操作 2.第一天造成一次伤害，此时1号5号灵魂仍然具有意志 3.第二天造成一次伤害。 4.第三天造成一次伤害。 5.第一天和第二天造成一次伤害，可以俘虏所有灵魂。(√) 6.第一天和第三天造成一次伤害。 7.第二天和第三天造成一次伤害，第6,7方案均会使得5号灵魂具有意志 8.一，二，三天均造成伤害。(√) #### 数据范围 对于30%的数据，有D ≤ n ≤ 16 对于50%的数据，有D ≤ n ≤ 50, ∑ ai ≤ 1000, max(di) + max(ti) ≤ 1000 对于70%的数据，有D ≤ 50, n ≤ 100, ∑ ai ≤ 10000 对于100%的数据，有∑ ai ≤ 20000, D ≤ min(100, n), n ≤ 10000, 1 ≤ ai ≤ 3000, 1 ≤ di , ti ≤ 20000, 1 ≤ ci ≤ n且保证 ci 互不相同