奥卡贝喜欢散步，但知道本组织的间谍可能在任何地方；这就是为什么他想知道在他的城市里他可以安全地走多少不同的路。
奥卡贝的城市可以表示为所有点(x, y) 使得x和y是非负的。
奥卡贝开始于原点(0,0)并且需要到达点(k,0)。
如果奥卡贝当前在点(x,y)，那么他下一步可以走到(x+1,y-1)或者(x+1,y)或者(x+1,y+1)。
此外，还有n条水平线段，其中第i条从x=ai开始到x=bi结束，并且位于y=ci。
保证a1=0,an<=k<=bn。
奥卡贝只能在每条线段的下方或恰好线段上行走，如果走到线段上方是不合法的。
奥卡贝现在想知道从原点到点(k,0)的方案数，输出方案数对1e9+7的模数。