시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 107 | 60 | 52 | 61.905% |
문자열 S와 P가 주어졌을 때, S에서 P를 하나 또는 그 이상 찾는 방법의 수를 구하는 프로그램을 작성하시오. 이때, S에서 찾은 P의 시작 위치를 모두 곱한 수가 1부터 9까지의 자연수로 모두 나누어 떨어져야 한다.
예를 들어, P = "a", S = "aaaaaaa"인 경우에, 문제의 조건에 맞는 방법은 {1, 2, 3, 4, 5, 6, 7}, {2, 3, 4, 5, 6, 7}, {3, 4, 5, 6, 7}, {1, 3, 4, 5, 6, 7} 이 있다.
첫째 줄에 P가, 둘째 줄에 S가 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 10,000을 넘지 않는 자연수이다.
첫째 줄에 문제의 조건대로 찾는 방법의 수를 109+7로 나눈 나머지를 출력한다.
a aaaaaaa
4
aa aaaaaaaaaaaaaaaaa
35544
aa aaaaaaaacaaaadaaafajaiaaaaaa
53712