Exista si $N$ puncte unde poti pune cate o zambila. Taurii isi vor stabili traseul astfel incat sa viziteze toate zambilele puse de tine. Pentru a nu crea confuzie, trebuie sa alegi punctele unde pui zambilele astfel incat toate sa fie vizitabile intr-o singura parcurgere a campului, avand in vedere restrictia de mers doar in $Nord$ si $Est$ a taurilor. Am uitat sa precizez: Ollu si Bollu sunt cei mai destepti tauri, ei isi dau seama rapid cand incerci sa ii pacalesti. Din acest motiv, nu poti pune mai putine zambile decat numarul de maxim de zambile pe care le-ai putea pune in cea mai favorabila alegere a punctelor - altfel i-ai irita foarte tare pe Ollu si Bollu.

Pentru toate modurile corecte in care ai putea alege setul de puncte unde sa pui zambile din cele $N$, Bisisica (un fel de Miorita, doar ca mai incapatanata) calculeaza cantitatea de iarba pe care o vor taia taurii cu firul lor daca isi propun sa viziteze zambilele alese. La final, ea aduna toate aceste numere iar pe suma o denumeste cu numele sau. Care este restul la impartirea cu $10^9^ + 7$ a numarului ei?

Pentru toate modurile corecte in care ai putea alege setul de puncte unde sa pui zambile, Bisisica (un fel de Miorita, doar ca mai incapatanata) calculeaza cantitatea de iarba pe care o vor taia taurii cu firul lor daca isi propun sa viziteze zambilele alese. La final, ea aduna toate aceste numere iar pe suma o denumeste cu numele sau. Care este restul la impartirea cu $10^9^ + 7$ a numarului ei?

h2. Date de intrare

* Pentru ~10% din punctaj, $N ≤ 16$
* Pentru ~20% din punctaj, $N ≤ 1.000$
* Pentru ~70% din punctaj, $N ≤ 50.000$

* Formal, un mod corect in care ai putea alege setul de puncte unde sa pui zambile corespunde unei submultimi de cardinal maxim a multimii de $N$ puncte date, astfel incat exista o ordonare a punctelor alese in asa fel incat coordonatele $X$, respectiv $Y$, sa fie simultan in ordine nedescrescatoare.

h2. Exemplu