Masala #R9CMKZS2LQ
Sanash o'tmaydi
Jahonali o'z yolida NxM tortburchakni uchiratdi. U boshida shu tortburchakning ichida nechta tortburchak bo'r ekanligin to'pmoqchi edi. Agar masala shu bilan tamomlanganda, masala juda oson bo'lar edi, shuning uchun qoshimcha 2 ta qora dog' bo'r.
Sizning maqsadingiz, shu tortburchakning ichiga nechta turli tortburchak qora dog'ni ichiga olmaydiganin topish.
Bo'shqacha aytganda, nechta turli \(1 \le X_1, X_2 \le N\) va \(1\le Y_1, Y_2 \le M\) \((X_1 \le X_2, Y_1 \le Y_2)\) tanglasa boladi, hech qanaqa \(X_1 \le i \le X_2\) va \(Y_1 \le j \le Y_2\) uchun \((i, j)\) qora dog' bolmaydi.
Birinchi qatorda N va M sonlari \((2\le N, M \le 1000)\)
Keyingi ikki qatorda X va Y, qora dog'lar koordinatalari \((1\le X \le N, 1 \le Y \le M)\)
Ikki turli koordinata berilishi kafolatlanadi.
NxM torburchakning ichida qora dog'ni ichiga olmaydigan to'rtburchaklar soni.
javobni \(10^9+7\) ga bo'lgandagi qoldiqni chop eting
# | input.txt | output.txt |
---|---|---|
1 |
2 2 1 2 2 1 |
2 |