该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

回声（echo）

题目描述

猪猪研究一种递归生成的颜色序列。

定义序列 $C_1$ 的长度为 $L_1=1$，且 $C_1=[1]$。

对于 $t\ge 1$，若已经得到长度为 $L_t$ 的序列 $C_t$，则序列 $C_{t+1}$ 由三部分依次拼接而成：

• 第一部分为一个完整的 $C_t$；
• 第二部分为连续 $L_t+1$ 个颜色 $t+1$；
• 第三部分为一个完整的 $C_t$。

因此有 $L_{t+1}=3L_t+1$。

例如：

现在给定 $n$，猪猪会进行 $q$ 次询问。每次询问给定三个整数 $c,l,r$，表示考虑序列 $C_n$ 的连续子段 $C_n[l],C_n[l+1],\ldots,C_n[r]$。

将这个子段重新编号为 $1,2,\ldots,r-l+1$。设颜色为 $c$ 的位置集合为

猪猪想知道，有多少个有序二元组 $(x,y)$ 满足：

由于答案可能很大，请对 $998244353$ 取模输出。

输入格式

第一行包含两个整数 $n,q$。

接下来 $q$ 行，每行包含三个整数 $c,l,r$，表示一次询问。

输出格式

输出 $q$ 行，第 $i$ 行输出第 $i$ 次询问的答案对 $998244353$ 取模后的结果。

样例

样例输入 #1

3 5
1 1 13
2 2 3
2 2 4
3 5 9
1 2 13

样例输出 #1

0
1
1
10
2

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le n\le 40$，$1\le q\le 8000$，$1\le c\le n$，$1\le l\le r\le L_n$。

• 特殊性质 A：保证所有询问均满足 $l=1$。
• 特殊性质 B：保证所有询问均满足 $c=n$。