CF954F Runner's Problem

You are running through a rectangular field. This field can be represented as a matrix with $ 3 $ rows and $ m $ columns. $ (i,j) $ denotes a cell belonging to $ i $ -th row and $ j $ -th column. You start in $ (2,1) $ and have to end your path in $ (2,m) $ . From the cell $ (i,j) $ you may advance to: - $ (i-1,j+1) $ — only if $ i>1 $ , - $ (i,j+1) $ , or - $ (i+1,j+1) $ — only if $ i<3 $ . However, there are $ n $ obstacles blocking your path. $ k $ -th obstacle is denoted by three integers $ a_{k} $ , $ l_{k} $ and $ r_{k} $ , and it forbids entering any cell $ (a_{k},j) $ such that $ l_{k}

The first line contains two integers $ n $ and $ m $ ( $ 1

Print the number of different paths from $ (2,1) $ to $ (2,m) $ , taken modulo $ 10^{9}+7 $ . If it is impossible to get from $ (2,1) $ to $ (2,m) $ , then the number of paths is $ 0 $ .