Count Distinct Routes

There are \( n \) towns numbered from \( 1 \) to \( n \), connected by \( m \) one-way roads. The competition starts at town \( 1 \) and ends at town \( 2 \). The organizers want to know how many distinct routes exist from town \( 1 \) to town \( 2 \).

Note: It is guaranteed that the input graph does not contain cycles, so the number of routes is finite.

inputFormat

The first line contains two integers \( n \) and \( m \) — the number of towns and the number of roads, respectively.

Each of the following \( m \) lines contains two integers \( u \) and \( v \), indicating there is a one-way road from town \( u \) to town \( v \).

outputFormat

Output a single integer representing the total number of distinct routes from town \( 1 \) to town \( 2 \). It is guaranteed that the answer fits in a 64-bit signed integer.

sample

2 1
1 2

1