문제
나락도 락이고, 부모님께 온 연락도 락이고, 오락가락?도 락?이지만?, 아쉽게도 쿼리는 락이 아니다.
알파벳 대문자로 이루어진 길이 $N$의 문자열 $S=s_{1} s_{2} \ldots s_{N}$가 주어진다. 이때, 다음과 같은 쿼리를 $Q$번 처리해야 한다.
- 1ドル$ $idx$ $c$: $s_{idx}$를 $c$로 변경한다. $(1 \leq idx \leq N,\ c$는 알파벳 대문자$)$
- 2ドル$ $l$ $r$: $s_{l} s_{l+1} \ldots s_{r}$의 부분열 중
ROCK으로 끝나는 문자열의 개수를 출력한다. 단, 수가 매우 클 수 있으니 10ドル^9+7$로 나눈 나머지를 출력한다. $(1 \leq l \leq r \leq N)$
출력
2ドル$번 쿼리에 대해 정답을 한 줄에 하나씩 출력한다.
노트
문자열의 부분열이란 문자열에서 0ドル$개 이상의 문자를 지운 문자열을 의미한다. 예를 들어, aan은 hanyang의 부분열이다.
W3sicHJvYmxlbV9pZCI6IjMwODgwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjZmZjXHViOWFjXHViMjk0IFx1Yjc3ZFx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQiLCJkZXNjcmlwdGlvbiI6IjxibG9ja3F1b3RlPlxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48c3Ryb25nPlx1YjA5OFx1Yjc3ZFx1YjNjNCBcdWI3N2RcdWM3NzRcdWFjZTAsIFx1YmQ4MFx1YmFhOFx1YjJkOFx1YWVkOCBcdWM2MjggXHVjNWYwXHViNzdkXHViM2M0IFx1Yjc3ZFx1Yzc3NFx1YWNlMCwgXHVjNjI0XHViNzdkXHVhYzAwXHViNzdkP1x1YjNjNCBcdWI3N2Q/XHVjNzc0XHVjOWMwXHViOWNjPywgXHVjNTQ0XHVjMjdkXHVhYzhjXHViM2M0IFx1Y2ZmY1x1YjlhY1x1YjI5NCBcdWI3N2RcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3N0cm9uZz48XC9wPlxyXG48XC9ibG9ja3F1b3RlPlxyXG5cclxuPHA+XHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhZTM4XHVjNzc0ICROJFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjQgJFM9c197MX0gc197Mn0gXFxsZG90cyBzX3tOfSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjZmZjXHViOWFjXHViOTdjICRRJFx1YmM4OCBcdWNjOThcdWI5YWNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiQxJCAkaWR4JCAkYyQ6ICRzX3tpZHh9JFx1Yjk3YyAkYyRcdWI4NWMgXHViY2MwXHVhY2JkXHVkNTVjXHViMmU0LiAkKDEgXFxsZXEgaWR4IFxcbGVxIE4sXFwgYyRcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MCQpJDxcL2xpPlxyXG5cdDxsaT4kMiQgJGwkICRyJDogJHNfe2x9IHNfe2wrMX0gXFxsZG90cyBzX3tyfSRcdWM3NTggXHViZDgwXHViZDg0XHVjNWY0IFx1YzkxMSA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+Uk9DSzxcL2NvZGU+PFwvc3Bhbj5cdWM3M2NcdWI4NWMgXHViMDVkXHViMDk4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZTgsIFx1YzIxOFx1YWMwMCBcdWI5ZTRcdWM2YjAgXHVkMDc0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWIyYzggJDEwXjkrNyRcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuICQoMSBcXGxlcSBsIFxcbGVxIHIgXFxsZXEgTikkPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmIzOFx1Yzc5MFx1YzVmNCAkUyRcdWM3NTggXHVhZTM4XHVjNzc0ICROJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoNCBcXGxlcSBOIFxcbGVxIDI1MDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNCAkUyRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMzggXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNmZmNcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4ICRRJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMSBcXGxlcSBRIFxcbGVxIDI1MDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YjEyNCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwICRRJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1Y2ZmY1x1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1Y2ZmY1x1YjlhY1x1YjI5NCAkMiRcdWJjODggXHVjZmZjXHViOWFjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiQyJFx1YmM4OCBcdWNmZmNcdWI5YWNcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzgxNVx1YjJmNVx1Yzc0NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWJkODBcdWJkODRcdWM1ZjRcdWM3NzRcdWI3ODAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHVjMTFjICQwJFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHViYjM4XHVjNzkwXHViOTdjIFx1YzljMFx1YzZiNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+YWFuPFwvY29kZT48XC9zcGFuPlx1Yzc0MCA8Y29kZT48c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+aGFueWFuZzxcL3NwYW4+PFwvY29kZT5cdWM3NTggXHViZDgwXHViZDg0XHVjNWY0XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzA4ODAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJRdWVyeSBJc25cdTIwMTl0IFJPQ0siLCJkZXNjcmlwdGlvbiI6IjxibG9ja3F1b3RlPlxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48c3Ryb25nPkR3YXluZSBKb2huc29uIGlzIHRoZSBST0NLLiBTaXN5cGh1cyBwdXNoaW5nIGEgcm9jayBpcyBST0NLLiBCb2NjaGkgdGhlIFJvY2sgaXMgUk9DSy4gSG93ZXZlciwgcXVlcnkgaXNuJiMzOTt0IFJPQ0suLi48XC9zdHJvbmc+PFwvcD5cclxuPFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPkdpdmVuIGEgc3RyaW5nICRTPXNfezF9IHNfezJ9IFxcbGRvdHMgc197Tn0kIG9mIGxlbmd0aCAkTiQgY29uc2lzdGluZyBvZiBvbmx5IEVuZ2xpc2ggdXBwZXJjYXNlIGxldHRlcnMsIHBlcmZvcm0gdGhlIGZvbGxvd2luZyBxdWVyaWVzICRRJCB0aW1lcy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kMSQgJGlkeCQgJGMkOiBDaGFuZ2UgJHNfe2lkeH0kIHRvICRjJC4gJCgxIFxcbGVxIGlkeCBcXGxlcSBOLFxcIGMkIGlzIGFuIEVuZ2xpc2ggdXBwZXJjYXNlIGxldHRlciQpJDxcL2xpPlxyXG5cdDxsaT4kMiQgJGwkICRyJDogUHJpbnQgdGhlIG51bWJlciBvZiBzdWJzZXF1ZW5jZXMgaW4gJHNfe2x9IHNfe2wrMX0gXFxsZG90cyBzX3tyfSQgZW5kaW5nIHdpdGggPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPlJPQ0s8XC9jb2RlPjxcL3NwYW4+LiBTaW5jZSB0aGlzIG51bWJlciBtYXkgYmUgbGFyZ2UsIHByaW50IGl0IG1vZHVsbyAkMTBeOSs3JC4gJCgxIFxcbGVxIGwgXFxsZXEgciBcXGxlcSBOKSQ8XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciAkTiQsIGRlbm90aW5nIHRoZSBsZW5ndGggb2YgdGhlIHN0cmluZyAkUyQuICQoNCBcXGxlcSBOIFxcbGVxIDI1MFxcOzAwMCkkPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgc3RyaW5nICRTJCBjb25zaXN0aW5nIG9mIG9ubHkgRW5nbGlzaCB1cHBlcmNhc2UgbGV0dGVycy48XC9wPlxyXG5cclxuPHA+VGhlIHRoaXJkIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciAkUSQsIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgcXVlcmllcy4gJCgxIFxcbGVxIFEgXFxsZXEgMjUwXFw7MDAwKSQ8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCAkUSQgbGluZXMgb2YgaW5wdXQgY29udGFpbnMgYSBxdWVyeS4gVGhlIGxhc3QgcXVlcnkgaXMgYSBxdWVyeSBvZiB0eXBlICQyJC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBxdWVyeSBvZiB0eXBlICQyJCwgcHJpbnQgdGhlIHJlc3VsdCBpbiBlYWNoIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IjxwPkEgc3Vic2VxdWVuY2Ugb2YgYSBzdHJpbmcgaXMgYSBzdHJpbmcgdGhhdCBjYW4gYmUgZm9ybWVkIGJ5IHJlbW92aW5nICQwJCBvciBtb3JlIGNoYXJhY3RlcnMgZnJvbSB0aGUgb3JpZ2luYWwgc3RyaW5nLiBGb3IgZXhhbXBsZSwgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPmFhbjxcL2NvZGU+PFwvc3Bhbj4gaXMgYSBzdWJzZXF1ZW5jZSBvZiA8Y29kZT48c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+aGFueWFuZzxcL3NwYW4+PFwvY29kZT4uPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d