142536, 10203 과 같이 수들이 ↗(증가), ↘(감소)또는 ↘(감소), ↗(증가)를 반복하는 수열을 지그재그 수열이라고 한다.

1232546은 123이 연속하여 증가만 하므로 지그재그 수열이 될 수 없다.

두 자리 지그재그 수열은 81개 존재하고 편의상 1자리 수는 모두 지그재그 수열이라고 가정한다.

두 수 A, B ( 1 <= A <= B < 10 ^100000)를 입력 받아 A부터 B까지 정수 중에 지그재그 수열인 정수의 개수를 구하시오.

결과 값이 너무 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

지그재그 수열2 timer 1s memory 64MB

지그재그 수열2 1s 64MB