[The original version of this problem (in Spanish) can be found at http://www.dc.uba.ar/events/icpc/download/problems/tap2013-problems.pdf]

Once upon a time there was a very joyous girl who was called Little Red-Cap because she always wore a red riding cap. Red-Cap enjoyed a lot her strolls in the woods, during which she collected berries in her small basket to offer them to her grandmother, who was known to prepare the most delicious pies of all the region. However, Red-Cap definitely did not enjoy the perils of the woods, and in particular the Big Bad Wolf who was always hungry and prying.

One day, Red-Cap decides to go from her home to that of her grandmother, collecting berries on the way and trying to make her journey in the safest possible way. Red-Cap's house is in a clearing at the westernmost point of the woods, her grandmother's house is in another clearing at the easternmost point, and inside the woods between them there are some other clearings containing berry trees. The woods are very dense, so the only way to go through them is using the pathways between the clearings, which fortunately Red-Cap knows very well. In order not to get lost, Red-Cap always moves through pathways that take her to a point strictly to the east of the point where she is. In order not to be caught by the wolf Red-Cap finds it imperative to avoid an ambush, and for that reason she always has in mind the number of different paths that take her from her current position to her grandmother's home.

A path in the woods is a sequence of clearings ordered from west to east, such that each clearing is connected with the next by a pathway. A path to the house of Red-Cap's grandmother is simply a path whose last clearing contains said house. For each clearing, its level of alternatives is the number of paths that go from it to Red-Cap's grandmother's house. In turn, for each path its level of alternatives is the sum of the levels of alternatives of all the clearings that make up that path. In order not to be captured by the wolf, Red-Cap wants to find the path with a maximum level of alternatives, starting at her house and ending at her grandmother's house. Can you help her?

 

Input

The first line contains two integer numbers N and S which respectively indicate the number of clearings and the number of pathways in the woods (3 ≤ N ≤ 3 × 10⁴ and 2 ≤ S ≤ 10⁵). The clearings are identified by different integer numbers between 1 and N, and are ordered from west to east, so that if 1 ≤ i < j ≤ N then clearing i is to the west of clearing j. Red-Cap's house is in clearing 1, whereas her grandmother's house is in clearing N.

Each of the following S lines describes a pathway using two integer numbers I and J, which indicate that there is a pathway between clearing I and clearing J (1 ≤ I < J ≤ N). There is at least one path from Red-Cap's house to her grandmother's house, and the maximum level of alternatives among the set of all such paths is no greater than 10¹⁸.

 

Output

Print a single line containing an integer number, representing the maximum level of alternatives for a path from Red-Cap's house to her grandmother's house.

 

Example 1

Input:
3 2
1 2
2 3
Output:
3

</p>

Example 2

Input:
4 6
1 2
2 3
3 4
1 2
2 3
3 4
Output:
15

</p>

Example 3

Input:
9 9
1 3
2 3
3 4
4 5
1 5
3 4
3 9
7 8
4 9
Output:
8

</p>