Problem 433: Statues

“Lulu was one of the picturesque characters of Cluj in the 70s and 90s. More recognizable than most personalities of the time. He deserves to be remembered by a statue at the bus station.”

The Info(1)cup Kingdom consists of $n$ towns, numbered from $1$ to $n$ . Lulu dreams of being the ruler of the Info(1)cup Kingdom, so he began making plans to honour himself before he even becomes the ruler. He wants to build statues of himself in all of the towns, however he doesn’t want to be too suspicious. As a consequence, he will build only one statue each day. On day $i$ he will build a statue in town $d_i$ . Moreover, he must satisfy $q$ different restrictions of type $(x, y)$ , meaning that all of the statues in the towns from $x$ to $y$ must be built after all of the statues in the towns from $1$ to $x-1$ . He is now wondering how many ways are there to build such statues in the $n$ towns, modulo $1 \ 000 \ 003$ .

Input data

The first line of the input will contain integers $n$ and $q$ , the number of towns and the number of restrictions respectively. The next $q$ lines each contain a restriction of type $(x, y)$ .

Output data

Output the number of ways to build the statues in the towns, modulo $1 \ 000 \ 003$ . In other words, output the remainder of the number of ways to build statues in the towns when divided by $1 \ 000 \ 003$ .

Restrictions

$1 ≤ n ≤ 10^{10}$
$1 ≤ q ≤ 2 \times 10^5$
$1 ≤ x ≤ y ≤ n$

Subtask 1 (7 points)

$n ≤ 9$

Subtask 2 (11 points)

$n ≤ 17$

Subtask 3 (6 points)

$q = 1$

Subtask 4 (9 points)

$n ≤ 10^6$ and $y = n$ for each restriction

Subtask 5 (15 points)

$n ≤ 10^6$ and $y_i < x_{i+1}$ for all $1 ≤ i < q$

Subtask 6 (25 points)

$n ≤ 10^6$

Subtask 7 (27 points)

No further restrictions

Examples

stdin

4 1
2 3

stdout