Бұл күрделі нұсқа. Нұсқалар арасындағы айырмашылықтар $N$-ға қойылатын шектеулерде жатыр.

Қазына орны бар, оны картада $N\times N$ өлшеміндегі тор ретінде көрсетуге болады. Бұл жерде кейбір ұяшықтарда бағалы ежелгі монеталар бар.

Витя — монета жинаушы. Ол қазына орнына $(1,1)$ бұрыштық ұяшығынан кірді. Ол қазына орнынан $(N,N)$ ұяшығынан шығып кеткенше оңға немесе төменге қарай қозғала береді. Витяда металды детектор құрылғысы бар және ол жолында кездескен барлық монеталарды жинайтын болады.

Әрине, Витя жинаған монеталардың санын максимизациялағысы келеді. Сондықтан ол қазына орнына келмес бұрын қазына картасын алды. Карта монеталардың нақты орналасқан жерін көрсетпейді, бірақ Витяның мүмкіндігінше көп монета жинау үшін қандай маршрутты таңдау керектігін көрсетеді.

Картаны бұрынғы кейбір саяхатшылар жасаған және онда көрсетілген маршруттың мынадай ерекше қасиеті бар — ол оңай алынатын монетаны ешқашан өткізіп жібермейді. Оңға немесе төменге бару мүмкіндігі болғанда және дәл осы ұяшықтардың бірінде монета болса, маршрут сол ұяшыққа барады. Әйтпесе, маршрут кез келген мүмкін бағытты таңдай алады.

Жоғарыда аталған қасиетті қанағаттандыратын әлі де көп мүмкін маршруттар болуы мүмкін екенін ескере отырып, сіз ойланасыз: Витя орташа алғанда қанша монета жинайды, егер барлық маршруттардың тең ықтималды екенін есептесек?

Енгізу

Кіріс деректерінің бірінші жолында екі бүтін сан $N$ және $M$ ($2\le N\le 3\cdot {10}^5$, $0\le M\le 1000$) — тордың өлшемі және монета бар ұяшықтардың саны.

Келесі $M$ жолдың әрқайсысында екі бүтін сан $x$ және $y$ ($1\le x,y\le N$) — монета бар ұяшықтың координаттары. Витяның бастапқы ұяшығында $(1,1)$ және қазына орнының шығу ұяшығында $(N,N)$ монета жоқ екендігіне кепілдік беріледі. Сондай-ақ, берілген барлық ұяшық координаттарының бірегей екендігіне кепілдік беріледі.

Шығару

Жауаптың бүтін бөлшек түрінде $\frac{P}{Q}$ түрінде ұсынылуы мүмкін екенін дәлелдеуге болады, мұнда $P\ge 0,Q>0$. Сізге $P\times Q^{-1}mod({10}^9+7)$ мәнін шығару қажет.

Мысалдар

Енгізу 1

3 2
1 2
1 3

Жауап 1

2

Енгізу 2

3 3
1 2
1 3
2 1

Жауап 2

250000003

Енгізу 3

2 0

Жауап 3

0

Ескертпелер

Екінші мысалда $4$ ықтимал маршрут болуы мүмкін:

• $(1,1)-(1,2)-(1,3)-(2,3)-(3,3)$, бұл екі монета жинайды.

• $(1,1)-(2,1)-(3,1)-(3,2)-(3,3)$, бұл бір монета жинайды.

• $(1,1)-(2,1)-(2,2)-(2,3)-(3,3)$, бұл бір монета жинайды.

• $(1,1)-(2,1)-(2,2)-(3,2)-(3,3)$, бұл бір монета жинайды.

Сондықтан, жауап $\frac{5}{4}mod({10}^9+7)=5\times 4^{-1}mod({10}^9+7)=250000003$.