P5141 列队

本题是数据加强版，弱化版请参考 NOIP2017 DAY2 T3。 ~~好了吓吓你们~~

前段时间，k 小 l 参加了 CTYZ 高一的的军训。众所周知，军训的时候需要站方阵。 k 小 l 所在的队伍中有原本有蒟蒻（巨佬）$2\times N$ 个，然而现在的只剩 k 小 l 等少数巨佬和一些蒟蒻了。 巨佬 dwq：教官我还有今年 IOI 的最后一题没调完，我先回去把题切了。 教官：行，准假，过十分钟调完了就先回去休息吧。 蒟蒻 yz：教官我今天任务计划里的红题还没做完，我要回去做。 教官：你现在回去也调不出来，乖乖站♂好，不要老是想偷懒。 k 小 l 是一个热爱学习的男♀孩子，现在他发现，操场上只剩两列队了，原本两列的长度都为 $N$，并且这两列队还残缺不全，蒟蒻在第一列，巨佬在第二列，并且如果一行中有巨佬，其气场会导致旁边不敢站蒟蒻。 **就算是这样，仅存巨佬们的战斗力还是比蒟蒻们的战斗力大。（废话）** 在 CTYZ 里面，一列队战斗力值是这样定义的 $$Fight=\sum_{i=0}^{n-1} p_{i}\times2^{i}$$ 其中 $i$ 为行标号，从 $0$ 开始，$p_{i}=1/0$ 表示这一行是否有人， 现在 k 小 l 已经知道目前巨佬队伍的站队情况，现在他想问你，蒟蒻们有多少种可能的站队方式。 然而 k 小 l 觉得这样的太简单了，k 小 l 现在有 $M$ 个询问，每次会给你一个蒟蒻战斗力值范围 $[a,b]$ 和一个 $k$，表示他希望知道蒟蒻们的战斗力值在 $[a,b]$ 之间，战斗力值第 $k$ 大的蒟蒻站队方式的战斗力值，如果站队方式总数小于 $k$，那么输出 `POOR AFO!`。

第一行两个个整数 $N,M$ 表示队列有 $N$ 行，k 小 l 的询问有 $M$ 次。 第二行为一串 `01` 串，表示巨佬们的站队方式。 接下来 $M$ 行，每行三个数 $a_{i},b_{i},k_{i}$，表示 k 小 l 的询问。

输出 $M$ 行表示答案，k 小 l 特别良心，允许你对于这个战斗力取模 $20031102$ 输出。

对于 $50\%$ 的数据，$N\le20,M\le50$。 对于 $100\%$ 的数据，$N\le62,M\le5\times10^5$。 时限很松，请放心食用。