28253번 - 그 정수의 개수를 구해줘

문제

두 정수 $L, R$이 주어졌을 때, 닫힌구간 $[L, R]$에 속하는 정수 중 정수 $X$를 포함하고 있는 정수의 개수를 구하시오.

어떤 정수 $a$가 다른 정수 $b$를 포함한다는 것은 두 정수를 문자열로 보았을 때 $a$의 연속된 부분 문자열 중 $b$가 존재한다는 의미이다.

입력

첫 번째 줄에 두 정수 $L, R$이 공백으로 구분되어 주어진다. (1ドル \le L \le R < 10^{100000}$)

두 번째 줄에 $X$가 주어진다. (1ドル \le X < 10^{100}$)

정수 $L, R, X$에 대해 0ドル$으로 시작하는 경우는 입력으로 주어지지 않는다.

출력

닫힌구간 $[L, R]$에 속하는 정수 중 $X$를 포함하고 있는 정수의 개수를 998ドル\ 244\ 353$로 나눈 나머지를 출력한다.

제한

힌트