CF2204G Grid Path

You are given a grid with $ n $ rows (numbered from $ 1 $ to $ n $ from top to bottom) and $ m $ columns (numbered from $ 1 $ to $ m $ from left to right). You are controlling a chip that is initially in the cell $ (1, 1) $ . In one move, the chip can move left, right, or down (if the current cell is $ (x, y) $ , it can go to $ (x, y - 1) $ , $ (x, y + 1) $ , or $ (x + 1, y) $ ). The chip cannot leave the grid. You can make any number of moves (possibly zero). Let's define the path of a chip as the set of cells it visits at least once. Note that the order of visited cells doesn't matter. Your task is to calculate the number of possible paths. Since the answer might be large, print it modulo $ mod $ .

The only line contains three integers $ n $ , $ m $ , and $ mod $ ( $ 1 \le n \le 10^8 $ ; $ 1 \le m \le 150 $ ; $ 2 \le mod \le 10^9 $ ).

Print a single integer — the number of possible paths, taken modulo $ mod $ .