시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB78161334.211%

문제

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

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

예제 입력 2

3
2 3
1 2
1 a

예제 출력 2

10

예제 입력 3

3
1 2
a 3
1 b

예제 출력 3

11
W3sicHJvYmxlbV9pZCI6IjI4MjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NjhcdWMyMThcdWM3NTggXHViOWFjXHVkMTM0XHVhYzEyIiwiZGVzY3JpcHRpb24iOiI8cD5cdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQ1NjhcdWMyMThcdWI5N2MgXHVjNzkxXHVjMTMxXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG5pbnQgZnVuKCkge1xyXG4gICAgaW50IHJldCA9IDA7XHJcbiAgICBmb3IgKGludCBhID0gWDxzdWI+MTxcL3N1Yj47IGEgJmx0Oz0gWTxzdWI+MTxcL3N1Yj47ICsrYSlcclxuICAgICAgICBmb3IgKGludCBiID0gWDxzdWI+MjxcL3N1Yj47IGIgJmx0Oz0gWTxzdWI+MjxcL3N1Yj47ICsrYilcclxuICAgICAgICAuLi5cclxuICAgICAgICAgICAgZm9yIChpbnQgJmx0O24tdGgmZ3Q7ID0gWDxzdWI+TjxcL3N1Yj47ICZsdDtuLXRoJmd0OyAmbHQ7PSBZPHN1Yj5OPFwvc3ViPjsgKysmbHQ7bi10aCZndDspXHJcbiAgICAgICAgICAgICAgICByZXQgPSAocmV0ICsgMSkgICUgMTAwMDAwMDAwNztcclxuICAgIHJldHVybiByZXQ7XHJcbn1cclxuPFwvcHJlPlxyXG5cclxuPHA+Jmx0O04tdGgmZ3Q7XHViMjk0IFx1YzYwMVx1YzViNCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NTggTlx1YmM4OFx1YzlmOCBcdWMxOGNcdWJiMzhcdWM3OTBcdWM3NzRcdWIyZTQuIFg8c3ViPmk8XC9zdWI+XHVjNjQwIFk8c3ViPmk8XC9zdWI+XHViMjk0IDEwMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IFx1YjYxMFx1YjI5NCBcdWQ1NzRcdWIyZjkgXHViOGU4XHVkNTA0IFx1YmMxNFx1YWU2NSBcdWNhYmRcdWM1ZDBcdWMxMWMgXHViNGYxXHVjN2E1XHVkNTVjIFx1YmNjMFx1YzIxOFx1YWMwMCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgWDxzdWI+MzxcL3N1Yj5cdWM3NDAgYSwgYiwgXHViNjEwXHViMjk0IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gWDxzdWI+aTxcL3N1Yj5cdWM2NDAgWTxzdWI+aTxcL3N1Yj5cdWM5MTEgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OFx1YjI5NCBcdWJjYzBcdWMyMTggXHVjNzc0XHViOTg0XHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWM3NzRcdWJhNzAsIFx1Yzc3NFx1YjI5NCBcdWJhYThcdWI0ZTAgaVx1YzVkMCBcdWQ1NzRcdWIyZjlcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlg8c3ViPmk8XC9zdWI+LCBZPHN1Yj5pPFwvc3ViPlx1Yzc1OCBcdWFjMTJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkNTY4XHVjMjE4XHVjNzU4IFx1YjlhY1x1ZDEzNFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIChYPHN1Yj4xPFwvc3ViPiwgWTxzdWI+MTxcL3N1Yj4pID0gKDEsIDIpLCAoWDxzdWI+MjxcL3N1Yj4sIFk8c3ViPjI8XC9zdWI+KSA9IChhLCAzKSwgKFg8c3ViPjM8XC9zdWI+LCBZPHN1Yj4zPFwvc3ViPikgPSAoMSwgYilcdWI3N2NcdWJhNzQsIFx1ZDU2OFx1YzIxOFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG5pbnQgZnVuKCkge1xyXG4gICAgaW50IHJldCA9IDA7XHJcbiAgICBmb3IgKGludCBhID0gMTsgYSAmbHQ7PSAyOyArK2EpXHJcbiAgICAgICAgZm9yIChpbnQgYiA9IGE7IGIgJmx0Oz0gMzsgKytiKVxyXG4gICAgICAgICAgICBmb3IgKGludCBjID0gMTsgYyAmbHQ7PSBiOyArK2MpXHJcbiAgICAgICAgICAgICAgICByZXQgPSAocmV0ICsgMSkgICUgMTAwMDAwMDAwNztcclxuICAgIHJldHVybiByZXQ7XHJcbn1cclxuPFwvcHJlPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBOKDEgJmxlOyZuYnNwO04gJmxlOyAyNilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgWDxzdWI+aTxcL3N1Yj5cdWM2NDAgWTxzdWI+aTxcL3N1Yj5cdWFjMDAgWDxzdWI+MTxcL3N1Yj4gWTxzdWI+MTxcL3N1Yj5cdWJkODBcdWQxMzAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViOWNjXHVjNTdkIFg8c3ViPmk8XC9zdWI+XHVjNjQwIFk8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWM4MTVcdWMyMThcdWI3N2NcdWJhNzQgWDxzdWI+aTxcL3N1Yj4gJmxlOyBZPHN1Yj5pPFwvc3ViPlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDU2OFx1YzIxOFx1Yzc1OCBcdWI5YWNcdWQxMzRcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4MjYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGVU5LQ0lKQSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaGFzIHdyaXR0ZW4gdGhlIGZvbGxvd2luZyBmdW5jdGlvbjo8XC9wPlxyXG5cclxuPHByZT5cclxuaW50IGZ1bigpIHtcclxuICAgIGludCByZXQgPSAwO1xyXG4gICAgZm9yIChpbnQgYSA9IFg8c3ViPjE8XC9zdWI+OyBhICZsdDs9IFk8c3ViPjE8XC9zdWI+OyArK2EpXHJcbiAgICAgICAgZm9yIChpbnQgYiA9IFg8c3ViPjI8XC9zdWI+OyBiICZsdDs9IFk8c3ViPjI8XC9zdWI+OyArK2IpXHJcbiAgICAgICAgLi4uXHJcbiAgICAgICAgICAgIGZvciAoaW50ICZsdDtuLXRoJmd0OyA9IFg8c3ViPk48XC9zdWI+OyAmbHQ7bi10aCZndDsgJmx0Oz0gWTxzdWI+TjxcL3N1Yj47ICsrJmx0O24tdGgmZ3Q7KVxyXG4gICAgICAgICAgICAgICAgcmV0ID0gKHJldCArIDEpICAlIDEwMDAwMDAwMDc7XHJcbiAgICByZXR1cm4gcmV0O1xyXG59XHJcbjxcL3ByZT5cclxuXHJcbjxwPiZsdDtOLXRoJmd0OyBkZW5vdGVzIHRoZSBOdGggbG93ZXJjYXNlIGxldHRlciBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldC4gRWFjaCBYPHN1Yj5pPFwvc3ViPiBhbmQgWTxzdWI+aTxcL3N1Yj4gZGVub3RlcyBlaXRoZXIgYSBwb3NpdGl2ZSBpbnRlZ2VyIGxlc3MgdGhhbiBvciBlcXVhbCB0byAxMDAgMDAwIG9yIGEgbmFtZSBvZiBhIHZhcmlhYmxlIHRoYXQgc29tZSBvdXRlciBsb29wIGl0ZXJhdGVzIG92ZXIuIEZvciBleGFtcGxlLCBYPHN1Yj4zPFwvc3ViPiBjYW4gYmUgZWl0aGVyIGEsIGIsIG9yIGFuIGludGVnZXIgbGl0ZXJhbC4gQXQgbGVhc3Qgb25lIG9mIFg8c3ViPmk8XC9zdWI+IGFuZCBZPHN1Yj5pPFwvc3ViPiB3aWxsIGJlIGFuIGludGVnZXIgbGl0ZXJhbCAoaS5lLiBub3QgYSB2YXJpYWJsZSBuYW1lKSBmb3IgZXZlcnkgaS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Q29tcHV0ZSB0aGUgcmV0dXJuIHZhbHVlIG9mIHRoZSBmdW5jdGlvbi4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMjYpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgdGhlIG5leHQgTiBsaW5lcywgdGhlIGl0aCBsaW5lIGNvbnRhaW5zIFg8c3ViPmk8XC9zdWI+IGFuZCBZPHN1Yj5pPFwvc3ViPiwgc2VwYXJhdGVkIHdpdGggYSBzcGFjZS4gSWYgWDxzdWI+aTxcL3N1Yj4gYW5kIFk8c3ViPmk8XC9zdWI+IGFyZSBib3RoIGludGVnZXIgbGl0ZXJhbHMsIHRoZW4gWDxzdWI+aTxcL3N1Yj4gJmxlOyBZPHN1Yj5pPFwvc3ViPi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXR1cm4gdmFsdWUgb2YgdGhlIGZ1bmN0aW9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #2 5번