1852. [HDOJ5068]哈利波特与数学老师

【题目描述】

众所周知，哈利波特在霍格沃茨学习魔法。但是，仅仅学习魔法知识并不足以让他成为一名伟大的魔法师。哈利有时候也需要学习其他科目来提高自身的知识水平，例如文学，数学，英语甚至算法。

在霍格沃茨，所有教师都住在一座很高的城堡中。这座城堡非常特别。其中的每一层都有两扇门，每扇门后都有两条楼梯，分别通向更高一层（下称‘下一层’）的两扇门。并且如果你位于第i层的第j扇门处，你就只能从这扇门前往下一层。并且，这些楼梯还会发生一些更有趣（或者说‘更魔法’）的事情：有时楼梯会突然变成碎片（让前往下一层变得不可能），有时碎片又会合起来重新变成完整的楼梯。现在假设哈利在a层（正如你所知，哈利是一名英雄，所以他出于某种原因住在教师宿舍中），而他的数学老师在b层。有时候数学老师会叫哈利去他的房间。面对这些神奇的楼梯，哈利对如何去见数学老师感到迷惑。你能帮助哈利找出有多少种不折返的路径吗？你可以假设当哈利在路上时楼梯的状态不会改变。哈利可以以第a层的任意一扇门为起点，以第b层的任意一扇门为终点。由于哈利希望尽快到达，因此他不会向反方向走。最初所有的楼梯都是完好的。由于答案可能会很大，你需要输出它模1000000007的值。

【输入格式】

输入包含多组数据，你应该一直处理到文件结束。

对每组数据，第一行有两个整数n,m（2<=n<=50000,1<=m<=50000），代表城堡的层数和询问数量。接下来的m行每行有三个或四个整数。如果第一个整数op=0，那么接下来有两个整数a,b(1<=a<b<=n)，代表哈利和他数学老师的位置。否则接下来有三个整数x,y,z(1<=x<n,1<=y,z<=2)，代表连接第x层第y扇门和第x+1层第z扇门的楼梯改变了状态（如果它是完整的就变成碎片，如果它是碎片就变得完整）。

【输出格式】

对每个op=0的询问，输出一行一个整数，代表从a层到b层的路径数量模1000000007的值。

【样例输入】

3 1

0 1 3

3 2

1 2 1 1

0 1 3

【样例输出】

8

6

【来源】

BestCoder Round #14 1003 Harry And Math Teacher