시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 6 3 3 100.000%

문제

새로운 언어를 만들었다. 이 언어에서 '단어'는 아래 조건을 모두 만족하는 비어있지 않은 문자열이다.

  1. 영어 소문자 ('a'-'z'), 마침표 ('.'), 붙임표 ('-'), 그리고 별표 ('*') 로만 구성되어 있는 비어있지 않은 문자열
  2. 문자열에 포함된 연속한 세 글자가 모두 특수문자인 경우가 없는 문자열 (특수문자는 '.', '-', '*')
  3. 문자열에 포함된 연속한 세 글자가 모두 모음인 경우가 없는 문자열 (모음은 'a', 'e', 'i', 'o', 'u')
  4. 문자열에 포함된 연속한 세 글자가 자음/모음/특수문자 관계없이 모두 동일한 경우가 없는 문자열
  5. 첫 글자가 특수문자가 아니고 마지막 글자도 특수문자가 아닌 문자열

예를 들어, 길이가 1인 단어는 총 26가지가 있다. 영어 소문자 한 글자는 각각이 단어이다. 추가로, "boj", "i.am.coder", and "hello*world" 모두 단어이다. 하지만, "zzz", ".boj", "mioum", and "hello-.-world" 네 문자열은 단어가 아니다. 

양수 a, b가 주어졌을 때, 길이가 a이상 b이하인 단어의 개수를 구하는 프로그램을 작성하시오. 단, 수가 매우 클 수 있으므로 이 수를 (109 + 7)로 나눈 나머지를 출력한다.

입력

첫 줄에 두 정수 a와 b (1 ≤ a ≤ b ≤ 1018)가 주어진다.

출력

첫 줄에 길이가 a이상 b이하인 단어의 개수를 (109 + 7)로 나눈 나머지를 출력한다.

서브태스크 1 (5점)

  • 1 ≤ a ≤ b ≤ 5

서브태스크 2 (6점)

  • 1 ≤ a ≤ b ≤ 1,000

서브태스크 3 (9점)

  • 1 ≤ a ≤ b ≤ 1,000,000

서브태스크 4 (20점)

  • 1 ≤ a ≤ b ≤ 1018

예제 입력 1

1 1

예제 출력 1

26

예제 입력 2

1 2

예제 출력 2

702

예제 입력 3

4 5

예제 출력 3

16745010

예제 입력 4

28 28

예제 출력 4

9496760

예제 입력 5

999999999999999999 999999999999999999

예제 출력 5

415475129
W3sicHJvYmxlbV9pZCI6IjE1OTM1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMGM4XHViODVjXHVjNmI0IFx1YzViOFx1YzViNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGM4XHViODVjXHVjNmI0IFx1YzViOFx1YzViNFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1Yzc3NCBcdWM1YjhcdWM1YjRcdWM1ZDBcdWMxMWMmbmJzcDsmIzM5O1x1YjJlOFx1YzViNCYjMzk7XHViMjk0IFx1YzU0NFx1Yjc5OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViYWE4XHViNDUwIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWJlNDRcdWM1YjRcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWM2MDFcdWM1YjQgXHVjMThjXHViYjM4XHVjNzkwICgmIzM5O2EmIzM5Oy0mIzM5O3omIzM5OyksIFx1YjljOFx1Y2U2OFx1ZDQ1YyAoJiMzOTsuJiMzOTspLCBcdWJkOTlcdWM3ODRcdWQ0NWMgKCYjMzk7LSYjMzk7KSwgXHVhZGY4XHViOWFjXHVhY2UwIFx1YmNjNFx1ZDQ1YyAoJiMzOTsqJiMzOTspIFx1Yjg1Y1x1YjljYyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YmU0NFx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHViYjM4XHVjNzkwXHVjNWY0PFwvbGk+XHJcblx0PGxpPlx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MWMgXHVjNWYwXHVjMThkXHVkNTVjIFx1YzEzOCBcdWFlMDBcdWM3OTBcdWFjMDAgXHViYWE4XHViNDUwIFx1ZDJiOVx1YzIxOFx1YmIzOFx1Yzc5MFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNWM2XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNCAoXHVkMmI5XHVjMjE4XHViYjM4XHVjNzkwXHViMjk0ICYjMzk7LiYjMzk7LCAmIzM5Oy0mIzM5OywgJiMzOTsqJiMzOTspPFwvbGk+XHJcblx0PGxpPlx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MWMgXHVjNWYwXHVjMThkXHVkNTVjIFx1YzEzOCBcdWFlMDBcdWM3OTBcdWFjMDAgXHViYWE4XHViNDUwIFx1YmFhOFx1Yzc0Y1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNWM2XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNCAoXHViYWE4XHVjNzRjXHVjNzQwICYjMzk7YSYjMzk7LCAmIzM5O2UmIzM5OywgJiMzOTtpJiMzOTssICYjMzk7byYjMzk7LCAmIzM5O3UmIzM5Oyk8XC9saT5cclxuXHQ8bGk+XHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxYyBcdWM1ZjBcdWMxOGRcdWQ1NWMgXHVjMTM4IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWM3OTBcdWM3NGNcL1x1YmFhOFx1Yzc0Y1wvXHVkMmI5XHVjMjE4XHViYjM4XHVjNzkwIFx1YWQwMFx1YWNjNFx1YzVjNlx1Yzc3NCBcdWJhYThcdWI0NTAgXHViM2Q5XHVjNzdjXHVkNTVjIFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM1YzZcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0PFwvbGk+XHJcblx0PGxpPlx1Y2NhYiBcdWFlMDBcdWM3OTBcdWFjMDAmbmJzcDtcdWQyYjlcdWMyMThcdWJiMzhcdWM3OTBcdWFjMDAgXHVjNTQ0XHViMmM4XHVhY2UwIFx1YjljOFx1YzljMFx1YjljOSBcdWFlMDBcdWM3OTBcdWIzYzQgXHVkMmI5XHVjMjE4XHViYjM4XHVjNzkwXHVhYzAwIFx1YzU0NFx1YjJjYyBcdWJiMzhcdWM3OTBcdWM1ZjQ8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWFlMzhcdWM3NzRcdWFjMDAgMVx1Yzc3OCBcdWIyZThcdWM1YjRcdWIyOTQgXHVjZDFkIDI2XHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNjAxXHVjNWI0IFx1YzE4Y1x1YmIzOFx1Yzc5MCBcdWQ1NWMgXHVhZTAwXHVjNzkwXHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc3NCBcdWIyZThcdWM1YjRcdWM3NzRcdWIyZTQuIFx1Y2Q5NFx1YWMwMFx1Yjg1YywgJnF1b3Q7Ym9qJnF1b3Q7LCAmcXVvdDtpLmFtLmNvZGVyJnF1b3Q7LCBhbmQgJnF1b3Q7aGVsbG8qd29ybGQmcXVvdDsgXHViYWE4XHViNDUwIFx1YjJlOFx1YzViNFx1Yzc3NFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCAmcXVvdDt6enomcXVvdDssICZxdW90Oy5ib2omcXVvdDssICZxdW90O21pb3VtJnF1b3Q7LCBhbmQgJnF1b3Q7aGVsbG8tLi13b3JsZCZxdW90OyBcdWIxMjQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YjJlOFx1YzViNFx1YWMwMCBcdWM1NDRcdWIyYzhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzU5MVx1YzIxOCBhLCBiXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWUzOFx1Yzc3NFx1YWMwMCBhXHVjNzc0XHVjMGMxIGJcdWM3NzRcdWQ1NThcdWM3NzggXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDtcdWIyZTgsIFx1YzIxOFx1YWMwMCBcdWI5ZTRcdWM2YjAgXHVkMDc0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMgXHVjNzc0IFx1YzIxOFx1Yjk3YyAoMTA8c3VwPjk8XC9zdXA+ICsgNylcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggYVx1YzY0MCBiICgxICZsZTsgYSAmbGU7IGIgJmxlOyAxMDxzdXA+MTg8XC9zdXA+KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWFlMzhcdWM3NzRcdWFjMDAgYVx1Yzc3NFx1YzBjMSBiXHVjNzc0XHVkNTU4XHVjNzc4IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgKDEwPHN1cD45PFwvc3VwPiArIDcpXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCIsInN1YnRhc2sxIjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgYSAmbGU7IGIgJmxlOyA1PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMiI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IGEgJmxlOyBiICZsZTsmbmJzcDsxLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazMiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBhICZsZTsgYiAmbGU7Jm5ic3A7MSwwMDAsMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrNCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IGEgJmxlOyBiICZsZTsmbmJzcDsxMDxzdXA+MTg8XC9zdXA+PFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIxNTkzNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik5ldyBMYW5ndWFnZSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGhhdmUgZGVzaWduZWQgYSBuZXcgbGFuZ3VhZ2UuIEluIHRoaXMgbGFuZ3VhZ2UsIGEgd29yZCBpcyBkZWZpbmVkIGFzIGEgbm9uLWVtcHR5IHN0cmluZyB0aGF0IG1lZXRzIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9ucy48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5JdCBpcyBhIG5vbi1lbXB0eSBzdHJpbmcgdGhhdCBvbmx5IGNvbnRhaW5zIGxvd2VyLWNhc2UgRW5nbGlzaCBhbHBoYWJldHMgKCZsc3F1bzthJnJzcXVvOy0mbHNxdW87eiZyc3F1bzspIGFuZCBzb21lIG9mIHNwZWNpYWwgY2hhcmFjdGVycyAtLSBwZXJpb2RzICgmbHNxdW87LiZyc3F1bzspLCBoeXBoZW5zICgmbHNxdW87LSZsc3F1bzspLCBhbmQgYXN0ZXJpc2tzICgmbHNxdW87KiZsc3F1bzspLjxcL2xpPlxyXG5cdDxsaT5ObyB0aHJlZSBjb25zZWN1dGl2ZSBjaGFyYWN0ZXJzIGFyZSBhbGwgc3BlY2lhbCBjaGFyYWN0ZXJzIChzcGVjaWFsIGNoYXJhY3RlcnMgYXJlICZsc3F1bzsuJnJzcXVvOywgJmxzcXVvOy0mbHNxdW87LCBhbmQgJmxzcXVvOyombHNxdW87KS48XC9saT5cclxuXHQ8bGk+Tm8gdGhyZWUgY29uc2VjdXRpdmUgdm93ZWxzIGFyZSBmb3VuZCAodGhlcmUgYXJlIGZpdmUgdm93ZWxzOiAmbHNxdW87YSZyc3F1bzssJnJzcXVvO2UmcnNxdW87LCAmbHNxdW87aSZyc3F1bzssICZsc3F1bztvJnJzcXVvOywgJmxzcXVvO3UmcnNxdW87KS48XC9saT5cclxuXHQ8bGk+Tm8gdGhyZWUgY29uc2VjdXRpdmUgY2hhcmFjdGVycyBhcmUgb2YgdGhlIHNhbWUgY2hhcmFjdGVyIChyZWdhcmRsZXNzIG9mIHRoZW0gYmVpbmcgY29uc29uYW50cywgdm93ZWxzLCBhbmQgc3BlY2lhbHMpLjxcL2xpPlxyXG5cdDxsaT5OZWl0aGVyIHRoZSBmaXJzdCBjaGFyYWN0ZXIgbm9yIHRoZSBsYXN0IGNoYXJhY3RlciBpcyBhIHNwZWNpYWwgY2hhcmFjdGVyLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPkZvciBpbnN0YW5jZSwgdGhlcmUgYXJlIDI2IHZhbGlkIHdvcmRzIG9mIGxlbmd0aCAxIGluIHRoaXMgbGFuZ3VhZ2UgLS0gZWFjaCBsb3dlci1jYWVzIEVuZ2xpc2ggYWxwaGFiZXQgaXRzZWxmIGlzIGEgdmFsaWQgd29yZC4gSW4gYWRkaXRpb24sICZxdW90O2JvaiZxdW90OywgJnF1b3Q7aS5hbS5jb2RlciZxdW90OywgYW5kICZxdW90O2hlbGxvKndvcmxkJnF1b3Q7IChxdW90ZXMgZm9yIGNsYXJpdHkpIGFyZSB2YWxpZCB3b3Jkcywgd2hlcmVhcyAmcXVvdDt6enomcXVvdDssICZxdW90Oy5ib2omcXVvdDssICZxdW90O21pb3VtJnF1b3Q7LCBhbmQgJnF1b3Q7aGVsbG8tLi13b3JsZCZxdW90OyBhcmUgbm90IHZhbGlkIHdvcmRzLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0d28gcG9zaXRpdmUgaW50ZWdlcnMgYSwgYW5kIGIsIGNvbXB1dGUgdGhlIG51bWJlciBvZiB2YWxpZCB3b3JkcyBvZiBsZW5ndGhzIGJldHdlZW4gYSBhbmQgYiAoaW5jbHVzaXZlKS4gU2luY2UgdGhpcyBudW1iZXIgY2FuIGJlIHF1aXRlIGxhcmdlLCB5b3Ugc2hvdWxkIG91dHB1dCB0aGlzIG51bWJlciBtb2R1bG8gKDEwPHN1cD45PFwvc3VwPiArIDcpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgd2lsbCBjb250YWluIHR3byBpbnRlZ2VycyBhIGFuZCBiICgxICZsZTsgYSAmbGU7IGIgJmxlOyAxMDxzdXA+MTg8XC9zdXA+KS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBtdXN0IGNvbnRhaW4gdGhlIG51bWJlciBvZiB2YWxpZCB3b3JkcyBvZiBsZW5ndGhzIGJldHdlZW4gYSBhbmQgYiAoaW5jbHVzaXZlKSBtb2R1bG8gKDEwPHN1cD45PFwvc3VwPiArIDcpLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCIsInN1YnRhc2sxIjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgYSAmbGU7IGIgJmxlOyZuYnNwOzU8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2syIjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgYSAmbGU7IGIgJmxlOyZuYnNwOzEsMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMyI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IGEgJmxlOyBiICZsZTsmbmJzcDsxLDAwMCwwMDA8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2s0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgYSAmbGU7IGIgJmxlOyZuYnNwOzEwPHN1cD4xODxcL3N1cD48XC9saT5cclxuPFwvdWw+XHJcbiJ9XQ==

출처

  • 문제를 만든 사람: haden