Suvarıcılar
Fermer Conun geniş bir sahəsi var və o, bu sahənin bir hissəsində şirin qarğıdalı əkmək istəyir. Sahəni araşdırdıqdan sonra Con gördü ki, sahəsi (n − 1) * (n − 1) ölçüsündə kvadratdır. Cənub-qərb küncü (0, 0) koordinatında, şimal-şərq küncü isə (n - 1, n - 1) koordinatında yerləşir.
Bəzi tam ədədi koordinatlarda iki istiqamətli suvarıcılar var, hər biri su və gübrə səpir. (i, j) koordinatında yerləşən iki istiqamətli suvarıcı, ondan şimala və şərqə olan sahəyə su səpir və ondan cənuba və qərbə olan sahəyə gübrə səpir. Formal olaraq, o, n ≥ x ≥ i və n ≥ y ≥ j olan bütün koordinatlara su səpir və 0 ≤ x ≤ i və 0 ≤ y ≤ j olan bütün koordinatlara gübrə səpir.
Fermer Con, sahəsində tam ədədi künc koordinatlarına malik olan bəzi oxla düzülmüş düzbucaqlıda şirin qarğıdalı əkmək istəyir. Lakin şirin qarğıdalının böyüməsi üçün düzbucaqlının bütün nöqtələri iki istiqamətli suvarıcılarla həm suvarılmalı, həm də gübrələnməlidir. Və əlbəttə ki, düzbucaqlının müsbət sahəsi olmalıdır, əks halda fermer Con orada qarğıdalı yetişdirə bilməzdi!
Fermer Cona, şirin qarğıdalı yetişdirə biləcəyi müsbət sahəli düzbucaqlıların sayını müəyyən etməyə kömək edin. Bu rəqəm böyük ola biləcəyi üçün, bu rəqəmin 10^9 + 7 moduluna görə qalıqını çıxarın.
Giriş məlumatları
Birinci sətir n (1 ≤ n ≤ 10^5) - sahənin ölçüsünü ehtiva edir. Növbəti n sətirin hər biri iki tam ədəd ehtiva edir. Bu tam ədədlər i və j olduqda, burada 0 ≤ i, j ≤ n − 1, onlar (i, j) koordinatında yerləşən suvarıcını göstərir.
Hər sütunda və hər sırada dəqiq bir suvarıcı olduğu təmin edilir. Yəni eyni x koordinatına malik iki suvarıcı yoxdur və eyni y koordinatına malik iki suvarıcı yoxdur.
Çıxış məlumatları
Tək bir tam ədəd çıxarın: tamamilə suvarılan və tamamilə gübrələnən müsbət sahəli düzbucaqlıların sayını 10^9 + 7 moduluna görə.