Ташко игра онлајн игра на табла со R редици и C колони. Во играта, за секоја колона се познати две вредности Ti и Bi - кои означуваат дека е потребно да се постави точно една фигура во некое од првите Ti полиња (првите Ti редици) од колоната, и точно една фигура во некое од последните Bi полиња (редици), притоа водејќи сметка за тоа во секој ред од табелата да нема поставено повеќе од една фигура (т.е. може во секој ред да има или 0 или 1 фигура). Може да се поставуваат и други фигури (нормално, доколку не прекршуваат некој од условите дадени погоре).

Ташко ужива во играта, но се прашува кој е вкупниот број на начини на кои може да се постават фигури на таблата, така што се задоволени условите дадени погоре. Напишете програма која ќе го пресмета и отпечати резултатот по модул 1 000 000 007.

Влез

Во првиот ред се запишани два цели броеви R и C (3 <= R <= 200, 1 <= C <= 50), кои го означуваат бројот на редици и колони, соодветно.

Во секој од следните C редови се запишани по два цели броја Ti и Bi (1 <= Ti, Bi <= R, и Ti+Bi <= R) - кои означуваат дека, во колоната i, треба да има точно една фигура во првите Ti редици, и една фигура во последните Bi редици.

Забелешка:
Во тест случаи кои носат најмалку 15% од поените, ќе важи R*C <= 21.
Во други тест случаи кои носат најмалку 9% од поените, ќе важи C = 1.
Во други тест случаи кои носат најмалку 20% од поените, ќе важи R, C <= 10.

Излез

Отпечатете го бараниот бројот на начини, по модул 1 000 000 007. За дадени два цели броја А и B, A модул B го означува остатокот кој се добива при делење на A со B. На пример, бројот 7 станува 1 по модул 3.

Ограничувања

Временско ограничување: 500 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
7 3
2 1
1 2
3 4

излез
6

Објаснување: Во втората колона, треба да поставиме фигура во првиот ред (само тој избор го имаме), а за првата колона гледаме дека треба да се постави фигура во еден од првите 2 редици - имајќи предвид дека за втората колона немавме избор и поставивме веќе фигура во првиот ред, сега мораме да ставиме фигура во вториот ред (бидејќи во играта е дозволено најмногу една фигура во секој ред). За третата колона, гледаме дека треба да се постави фигура во еден од првите 3 редици, но знаејќи дека првите 2 се веќе зафатени, значи мора да ставиме фигура во третиот ред во таа колона.

Слично може да анализираме и за последните редици. Во првата колона мора да се постави фигура во последниот ред, во втората колона во претпоследниот ред (бидејќи имаме избор од два, но последниот ред е зафатен), а за третата колона имаме избор или да поставиме фигура во третиот ред гледано од долу, или во четвртиот ред гледано од долу. Доколку поставиме во третиот ред гледано од долу, постојат 3 опции за четвртиот ред гледано од долу (да не се постави ништо, да се постави фигура во првата колона или да се постави во втората колона) - овие опции се дадени во горниот дел од сликата дадена подолу. Слично, доколку ја поставиме фигурата во четвртиот ред гледано од долу, постојат 3 опции за третиот ред (овие опции се дадени во долниот дел од сликата дадена подолу). Значи, вкупно постојат 3+3=6 начини за поставување на фигурите.