卡特莉为了提高自己的知识水平，决定去图书馆借一些书来学习。

现在图书馆有顺序排列着编号1至n的分馆，每个分馆里的书籍都属于不同的知识领域。

由于图书馆刚刚新建，一开始所有的分馆都没有书籍。

但是随着时间的推移，其中的某个分馆会扩充自己的藏书。

并且在某个时刻卡特莉可能会去借书，由于她懒得走太远，她只会在编号在l至r之间的分馆借书，并且她每次不会在同一个领域借多本书籍（这就意味着她每次最多只会在一个分馆借一本书）。

每次她在借书之前希望知道自己有多少种方案能恰好借到k本书，请你每次帮她求出答案。

具体的来说，我们一共有n座分馆，一开始每个图书馆的藏书数量都为0。

接下来我们会有m个时刻。

我们按顺序给出这m个时刻的操作，每个时刻有一个op。

如果op=1，那么接下来输入pos，x，表示编号为pos的图书馆藏书增加x。

如果op=2，那么接下来输入l，r，k，表示查询从编号l至r的图书馆恰好借k本书的方案数。

我们认为所有的书都是不同的，两个方案之间只要有一本书不同我们就认为它们是不同的方案。

第一行输入一个T()表示数据组数。


接下来T组数据。

对于每组数据，第一行输入n，m()，分别表示图书馆的数量和时刻的数量。
接下来有m行，每行输入1，pos，x()或者2，l，r，k()。

对于每次查询，输出一个数字表示答案，由于答案可能很大，请将答案对取模后输出。
请注意，行末不要输出多余空格。

1
3 8
2 1 3 1
1 1 2
2 1 3 1
2 1 3 2
1 2 1
2 2 2 1
2 1 3 1
2 1 3 2

0
2
0
1
3
2