시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 45 7 6 66.667%

문제

창영이는 다음과 같은 함수를 작성했다.

int fun() {
    int ret = 0;
    for (int a = X1; a <= Y1; ++a)
        for (int b = X2; b <= Y2; ++b)
        ...
            for (int <n-th> = XN; <n-th> <= YN; ++<n-th>)
                ret = (ret + 1)  % 1000000007;
    return ret;
}

<N-th>는 영어 알파벳의 N번째 소문자이다. Xi와 Yi는 100,000보다 작거나 같은 양의 정수 또는 해당 루프 바깥 쪽에서 등장한 변수가 될 수 있다.

예를 들어, X3은 a, b, 또는 숫자가 될 수 있다. Xi와 Yi중 적어도 하나는 변수 이름이 아닌 숫자이며, 이는 모든 i에 해당된다.

Xi, Yi의 값이 주어졌을 때, 함수의 리턴값을 출력하는 프로그램을 작성하시오.

만약 (X1, Y1) = (1, 2), (X2, Y2) = (a, 3), (X3, Y3) = (1, b)라면, 함수는 다음과 같다.

int fun() {
    int ret = 0;
    for (int a = 1; a <= 2; ++a)
        for (int b = a; b <= 3; ++b)
            for (int c = 1; c <= b; ++c)
                ret = (ret + 1)  % 1000000007;
    return ret;
}

입력

첫째 줄에 양의 정수 N(1 ≤ N ≤ 26)이 주어진다. 다음 N개의 줄에는 Xi와 Yi가 X1 Y1부터 차례대로 주어진다. 만약 Xi와 Yi가 모두 숫자라면 Xi <= Yi이다.

출력

첫째 줄에 함수의 리턴값을 출력한다.

예제 입력 1

2
1 2
a 3

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjI4MjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NjhcdWMyMThcdWM3NTggXHViOWFjXHVkMTM0XHVhYzEyIiwiZGVzY3JpcHRpb24iOiI8cD5cdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQ1NjhcdWMyMThcdWI5N2MgXHVjNzkxXHVjMTMxXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cHJlIGNsYXNzPVwiYnJ1c2g6YysrOyB0b29sYmFyOmZhbHNlO1wiPlxyXG5pbnQgZnVuKCkge1xyXG4gICAgaW50IHJldCA9IDA7XHJcbiAgICBmb3IgKGludCBhID0gWDE7IGEgJmx0Oz0gWTE7ICsrYSlcclxuICAgICAgICBmb3IgKGludCBiID0gWDI7IGIgJmx0Oz0gWTI7ICsrYilcclxuICAgICAgICAuLi5cclxuICAgICAgICAgICAgZm9yIChpbnQgJmx0O24tdGgmZ3Q7ID0gWE47ICZsdDtuLXRoJmd0OyAmbHQ7PSBZTjsgKysmbHQ7bi10aCZndDspXHJcbiAgICAgICAgICAgICAgICByZXQgPSAocmV0ICsgMSkgICUgMTAwMDAwMDAwNztcclxuICAgIHJldHVybiByZXQ7XHJcbn1cclxuPFwvcHJlPlxyXG5cclxuPHA+Jmx0O04tdGgmZ3Q7XHViMjk0IFx1YzYwMVx1YzViNCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NTggTlx1YmM4OFx1YzlmOCBcdWMxOGNcdWJiMzhcdWM3OTBcdWM3NzRcdWIyZTQuIFg8c3ViPmk8XC9zdWI+XHVjNjQwIFk8c3ViPmk8XC9zdWI+XHViMjk0IDEwMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IFx1YjYxMFx1YjI5NCBcdWQ1NzRcdWIyZjkgXHViOGU4XHVkNTA0IFx1YmMxNFx1YWU2NSBcdWNhYmRcdWM1ZDBcdWMxMWMgXHViNGYxXHVjN2E1XHVkNTVjIFx1YmNjMFx1YzIxOFx1YWMwMCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgWDNcdWM3NDAgYSwgYiwgXHViNjEwXHViMjk0IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gWDxzdWI+aTxcL3N1Yj5cdWM2NDAgWTxzdWI+aTxcL3N1Yj5cdWM5MTEgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OFx1YjI5NCBcdWJjYzBcdWMyMTggXHVjNzc0XHViOTg0XHVjNzc0IFx1YzU0NFx1YjJjYyBcdWMyMmJcdWM3OTBcdWM3NzRcdWJhNzAsIFx1Yzc3NFx1YjI5NCBcdWJhYThcdWI0ZTAgaVx1YzVkMCBcdWQ1NzRcdWIyZjlcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlg8c3ViPmk8XC9zdWI+LCBZPHN1Yj5pPFwvc3ViPlx1Yzc1OCBcdWFjMTJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkNTY4XHVjMjE4XHVjNzU4IFx1YjlhY1x1ZDEzNFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIChYPHN1Yj4xPFwvc3ViPiwgWTxzdWI+MTxcL3N1Yj4pID0gKDEsIDIpLCAoWDxzdWI+MjxcL3N1Yj4sIFk8c3ViPjI8XC9zdWI+KSA9IChhLCAzKSwgKFg8c3ViPjM8XC9zdWI+LCBZPHN1Yj4zPFwvc3ViPikgPSAoMSwgYilcdWI3N2NcdWJhNzQsIFx1ZDU2OFx1YzIxOFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cHJlIGNsYXNzPVwiYnJ1c2g6YysrOyB0b29sYmFyOmZhbHNlO1wiPlxyXG5pbnQgZnVuKCkge1xyXG4gICAgaW50IHJldCA9IDA7XHJcbiAgICBmb3IgKGludCBhID0gMTsgYSAmbHQ7PSAyOyArK2EpXHJcbiAgICAgICAgZm9yIChpbnQgYiA9IGE7IGIgJmx0Oz0gMzsgKytiKVxyXG4gICAgICAgICAgICBmb3IgKGludCBjID0gMTsgYyAmbHQ7PSBiOyArK2MpXHJcbiAgICAgICAgICAgICAgICByZXQgPSAocmV0ICsgMSkgICUgMTAwMDAwMDAwNztcclxuICAgIHJldHVybiByZXQ7XHJcbn1cclxuPFwvcHJlPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBOKDEgJmxlOyZuYnNwO04gJmxlOyAyNilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgWDxzdWI+aTxcL3N1Yj5cdWM2NDAgWTxzdWI+aTxcL3N1Yj5cdWFjMDAgWDxzdWI+MTxcL3N1Yj4gWTxzdWI+MTxcL3N1Yj5cdWJkODBcdWQxMzAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViOWNjXHVjNTdkIFg8c3ViPmk8XC9zdWI+XHVjNjQwIFk8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWMyMmJcdWM3OTBcdWI3N2NcdWJhNzQgWDxzdWI+aTxcL3N1Yj4gJmx0Oz0gWTxzdWI+aTxcL3N1Yj5cdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1NjhcdWMyMThcdWM3NTggXHViOWFjXHVkMTM0XHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODI2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRlVOS0NJSkEiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGhhcyB3cml0dGVuIHRoZSBmb2xsb3dpbmcgZnVuY3Rpb246PFwvcD5cclxuXHJcbjxwcmU+XHJcbmludCBmdW4oKSB7XHJcbiAgICBpbnQgcmV0ID0gMDtcclxuICAgIGZvciAoaW50IGEgPSBYMTsgYSAmbHQ7PSBZMTsgKythKVxyXG4gICAgICAgIGZvciAoaW50IGIgPSBYMjsgYiAmbHQ7PSBZMjsgKytiKVxyXG4gICAgICAgIC4uLlxyXG4gICAgICAgICAgICBmb3IgKGludCAmbHQ7bi10aCZndDsgPSBYTjsgJmx0O24tdGgmZ3Q7ICZsdDs9IFlOOyArKyZsdDtuLXRoJmd0OylcclxuICAgICAgICAgICAgICAgIHJldCA9IChyZXQgKyAxKSAgJSAxMDAwMDAwMDA3O1xyXG4gICAgcmV0dXJuIHJldDtcclxufVxyXG48XC9wcmU+XHJcblxyXG48cD4mbHQ7Ti10aCZndDsgZGVub3RlcyB0aGUgTnRoIGxvd2VyY2FzZSBsZXR0ZXIgb2YgdGhlIEVuZ2xpc2ggYWxwaGFiZXQuIEVhY2ggWGkgYW5kIFlpIGRlbm90ZXMgZWl0aGVyIGEgcG9zaXRpdmUgaW50ZWdlciBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gMTAwIDAwMCBvciBhIG5hbWUgb2YgYSB2YXJpYWJsZSB0aGF0IHNvbWUgb3V0ZXIgbG9vcCBpdGVyYXRlcyBvdmVyLiBGb3IgZXhhbXBsZSwgWDMgY2FuIGJlIGVpdGhlciBhLCBiLCBvciBhbiBpbnRlZ2VyIGxpdGVyYWwuIEF0IGxlYXN0IG9uZSBvZiBYaSBhbmQgWWkgd2lsbCBiZSBhbiBpbnRlZ2VyIGxpdGVyYWwgKGkuZS4gbm90IGEgdmFyaWFibGUgbmFtZSkgZm9yIGV2ZXJ5IGkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkNvbXB1dGUgdGhlIHJldHVybiB2YWx1ZSBvZiB0aGUgZnVuY3Rpb24uJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDI2KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIHRoZSBuZXh0IE4gbGluZXMsIHRoZSBpdGggbGluZSBjb250YWlucyBYaSBhbmQgWWksIHNlcGFyYXRlZCB3aXRoIGEgc3BhY2UuIElmIFhpIGFuZCBZaSBhcmUgYm90aCBpbnRlZ2VyIGxpdGVyYWxzLCB0aGVuIFhpICZsZTsgWWkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmV0dXJuIHZhbHVlIG9mIHRoZSBmdW5jdGlvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d