How Many Shortest Paths?

Firstly, let's reverse the direction of all the edges.
Secondly, let's run $BFS$ from each node of the given sequence in the following order:
source of the first $BFS$ is $a_2$ and the target node is $a_1$. The second BFS source is $a_3$ and the target is $a_2$. The third $BFS$ source is $a_4$ and the target is $a_3$, and so on. And for the last $BFS$, the source would be node $a_x$ and the target would be node $a_{x-1}$. For each $BFS$, sum up the shortest path from the source node to the target node. If the target node is unreachable, print $-1$.
Thirdly, now we have to find the total number of ways. At the beginning of each $BFS$, the number of ways for the source node is 1. Every time we visit an unvisited node, just pass the number of ways of the parent node to the child node. If we encounter a visited node and the level of the visited node is the level of the current front node $+1$, add the number of ways of the front node to the visited node.
At the end of each $BFS$, multiply the total number of ways to reach the target node with an answer. Please don't forget to use modulo $100000110059$.