有一個數線從 $0$ 到 $m$，你一開始在位置 $0$ 上，想要搭公車到位置 $m$ 處。
有 $n$ 台公車路線可以選擇，每一公車路線都有其行駛的起點和終點。

例如你想要到位置 $m = 9$，且有 $n = 5$ 條公車路線如下

你可以任意地決定公車何時出發，並且在公車的路線範圍內都可以上車，但一定會搭到該路線的終點才下車，且不可在同一位置同時上下車。

你想知道總共有幾種搭車方式可以到位置 $m$。如上述例子總共有 $7$ 種搭車方式，分別如下列：
(1) 1 -> 2 -> 4 -> 5 (先搭乘路線1 到 位置 $4$，再搭乘路線2 到位置 $6$，接著搭乘路線4 到位置 $7$，最後搭乘路線5 到位置 $9$)
(2) 1 -> 2 -> 5
(3) 1 -> 3 -> 4 -> 5
(4) 1 -> 3 -> 5
(5) 1 -> 4 -> 5
(6) 3 -> 4 -> 5
(7) 3 -> 5

由於搭乘方式數量可能很大，請輸出搭乘方式數量 mod $p$ 的結果。