행운의 수
시간 제한0.2초메모리 제한1024 MB
자릿수 문자열 X에 한 자리 갱신이 섞인 질의가 주어질 때, X의 구간 값 이하이면서 13을 포함하지 않는 수의 개수를 10^9+7로 나눈 나머지로 구합니다.
문제
13이 불운을 가져온다고 여기는 문화가 있다는 것은 잘 알려져 있다.
N자리 수 X가 주어진다. X 이하의 음이 아닌 정수 중 10진 표현에 13이 부분 문자열로 포함되지 않는 수의 개수를 구하라. 답은 1 000 000 007로 나눈 나머지로 출력한다.
또한 Q개의 질의를 처리해야 한다. 질의는 두 종류이다.
- 질의(radixL, radixR): substr(X, radixL, radixR) 이하의 음이 아닌 정수 중 10진 표현에 13이 부분 문자열로 포함되지 않는 수의 개수를 구하라. 답은 1 000 000 007로 나눈 나머지로 출력한다. substr(X, L, R)은 X의 왼쪽에서 L번째 자리부터 R번째 자리까지의 부분 문자열이다.
- 갱신(radix, newDigit): 왼쪽에서 radix번째 자리의 숫자를 newDigit으로 바꾼다.
X의 번호는 1부터 시작한다. X와 substr(X, l, r)은 앞자리 0을 가질 수 있다.
입력
첫 줄에 두 정수 N과 Q(1 ≤ N ≤ 100 000, 0 ≤ Q ≤ 10 000)가 주어진다. N은 X의 자릿수이고, Q는 질의의 개수이다.
둘째 줄에 수 X가 주어진다.
이어지는 Q개의 줄에 질의가 하나씩 주어진다. 각 줄은 질의 종류 t(1 ≤ t ≤ 2)로 시작한다. t = 1이면 정수 radixL과 radixR(1 ≤ radixL ≤ radixR ≤ N)이 이어서 주어진다. t = 2이면 정수 radix와 newDigit(1 ≤ radix ≤ N, 0 ≤ newDigit ≤ 9)이 이어서 주어진다.
출력
첫 줄에 X 이하의 음이 아닌 정수 중 13을 부분 문자열로 포함하지 않는 수의 개수를 1 000 000 007로 나눈 나머지를 출력한다.
이후 종류 1인 질의마다 답을 1 000 000 007로 나눈 나머지를 한 줄에 하나씩 출력한다.
힌트
처음에 X는 560484이다. 560484 이하의 음이 아닌 정수 중 13을 부분 문자열로 포함하지 않는 수는 528145개이다. 여기에는 0도 포함된다.
갱신 "2 6 4" 후에도 X는 560484이다. "2 1 4" 후 X는 460484가 된다. "2 5 6" 후 X는 460464가 된다. "2 6 1" 후 X는 460461이 된다. "2 3 6" 후 X는 466461이 된다.
질의 "1 3 6"의 답은 6228이다. "1 1 3"의 답은 452이다. "1 6 6"의 답은 2이며, 이는 0과 1이다. "1 2 6"의 답은 63454이다. 갱신 "2 1 7" 후 X는 766461이 된다.