시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 37 10 9 39.130%

문제

양의 정수의 각 자리의 변화가 증가와 감소를 번갈아가면서 나타날 때, 이 숫자를 "지그재그 수"라고 한다. 예를 들어, 2947은 자리가 2→9→4→7로 증가→감소→증가 순이기 때문에 지그재그 수이다. 또, 71946은 감소→증가→감소→증가이기 때문에 지그재그 수이다. 하지만, 123, 71446, 71442, 88은 지그재그 수가 아니다. 한 자리 정수는 지그재그 수이다.

A이상 B이하의 M의 배수 중 지그재그 수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 M이 주어진다. (1 ≤ A ≤ B ≤ 10500, 1 ≤ M ≤ 500)

출력

A이상 B이하의 M의 배수 중 지그재그 수의 개수를 10000으로 나눈 나머지를 출력한다.

예제 입력 1

100
200
5

예제 출력 1

13

힌트

105, 120, 130, 140, 150, 160, 165, 170, 175, 180, 185, 190, 195

W3sicHJvYmxlbV9pZCI6IjU1NDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjggXHVjMjJiXHVjNzkwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzU4IFx1YWMwMSBcdWM3OTBcdWI5YWNcdWM3NTggXHViY2MwXHVkNjU0XHVhYzAwIFx1Yzk5ZFx1YWMwMFx1YzY0MCBcdWFjMTBcdWMxOGNcdWI5N2MgXHViYzg4XHVhYzA4XHVjNTQ0XHVhYzAwXHViYTc0XHVjMTFjIFx1YjA5OFx1ZDBjMFx1YjBhMCBcdWI1NGMsIFx1Yzc3NCBcdWMyMmJcdWM3OTBcdWI5N2MgJnF1b3Q7XHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzIxOCZxdW90O1x1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIDI5NDdcdWM3NDAgXHVjNzkwXHViOWFjXHVhYzAwIDImcmFycjs5JnJhcnI7NCZyYXJyOzdcdWI4NWMgXHVjOTlkXHVhYzAwJnJhcnI7XHVhYzEwXHVjMThjJnJhcnI7XHVjOTlkXHVhYzAwIFx1YzIxY1x1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViNjEwLCA3MTk0Nlx1Yzc0MCBcdWFjMTBcdWMxOGMmcmFycjtcdWM5OWRcdWFjMDAmcmFycjtcdWFjMTBcdWMxOGMmcmFycjtcdWM5OWRcdWFjMDBcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzljMFx1YWRmOFx1YzdhY1x1YWRmOCBcdWMyMThcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgMTIzLCA3MTQ0NiwgNzE0NDIsIDg4XHVjNzQwIFx1YzljMFx1YWRmOFx1YzdhY1x1YWRmOCBcdWMyMThcdWFjMDAgXHVjNTQ0XHViMmM4XHViMmU0LiBcdWQ1NWMgXHVjNzkwXHViOWFjIFx1YzgxNVx1YzIxOFx1YjI5NCBcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjggXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRBXHVjNzc0XHVjMGMxIEJcdWM3NzRcdWQ1NThcdWM3NTggTVx1Yzc1OCBcdWJjMzBcdWMyMTggXHVjOTExIFx1YzljMFx1YWRmOFx1YzdhY1x1YWRmOCBcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBBLCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIEIsIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDAgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQSAmbGU7IEIgJmxlOyAxMDxzdXA+NTAwPFwvc3VwPiwgMSAmbGU7IE0gJmxlOyA1MDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0QVx1Yzc3NFx1YzBjMSBCXHVjNzc0XHVkNTU4XHVjNzU4IE1cdWM3NTggXHViYzMwXHVjMjE4IFx1YzkxMSBcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjggXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyAxMDAwMFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHJcblx0MTA1LCAxMjAsIDEzMCwgMTQwLCAxNTAsIDE2MCwgMTY1LCAxNzAsIDE3NSwgMTgwLCAxODUsIDE5MCwgMTk1PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NTQ4IiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiXHUzMGI4XHUzMGIwXHUzMGI2XHUzMGIwXHU2NTcwIChaaWctWmFnIE51bWJlcnMpIiwiZGVzY3JpcHRpb24iOiI8cD5cdTZiNjNcdTMwNmVcdTY1NzRcdTY1NzBcdTMwOTIgKFx1NTE0OFx1OTgyZFx1MzA2YiAwIFx1MzA5Mlx1MzA2NFx1MzA1MVx1MzA1YVx1MzA2YikgMTAgXHU5MDMyXHU2Y2Q1XHUzMDY3XHU2NmY4XHUzMDQ0XHUzMDY2XHU2ODQxXHUzMDZlXHU2NTcwXHU1YjU3XHUzMDkyXHU5ODA2XHU3NTZhXHUzMDZiXHU4OThiXHUzMDY2XHUzMDQ0XHUzMDRmXHUzMDY4XHU1ODk3XHU1MmEwXHUzMDY4XHU2ZTFiXHU1YzExXHUzMDkyXHU0ZWE0XHU0ZTkyXHUzMDZiXHU3ZTcwXHUzMDhhXHU4ZmQ0XHUzMDU3XHUzMDY2XHUzMDQ0XHUzMDhiXHUzMDY4XHUzMDRkXHVmZjBjXHUzMDVkXHUzMDZlXHU2NTcwXHUzMDZmXHUzMDBjXHUzMGI4XHUzMGIwXHUzMGI2XHUzMGIwXHU2NTcwXHUzMDBkXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDY4XHU1NDdjXHUzMDc2XHUzMDUzXHUzMDY4XHUzMDZiXHUzMDU3XHUzMDg4XHUzMDQ2XHVmZjBlXHUzMDVmXHUzMDY4XHUzMDQ4XHUzMDcwXHVmZjBjMjk0NyBcdTMwNmZcdTY4NDFcdTMwNmVcdTY1NzBcdTViNTdcdTMwNGMgMiAmcmFycjsgOSAmcmFycjsgNCAmcmFycjsgNyBcdTMwNjhcdWZmMGNcdTU4OTdcdTUyYTAgJnJhcnI7IFx1NmUxYlx1NWMxMSAmcmFycjsgXHU1ODk3XHU1MmEwIFx1MzA2ZVx1OTgwNlx1MzA2Ylx1MzA2YVx1MzA2M1x1MzA2Nlx1MzA0NFx1MzA4Ylx1MzA2ZVx1MzA2N1x1MzBiOFx1MzBiMFx1MzBiNlx1MzBiMFx1NjU3MFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZVx1MzA3ZVx1MzA1Zlx1ZmYwYzcxOTQ2IFx1MzA2ZiBcdTZlMWJcdTVjMTEgJnJhcnI7IFx1NTg5N1x1NTJhMCAmcmFycjsgXHU2ZTFiXHU1YzExICZyYXJyOyBcdTU4OTdcdTUyYTAgXHUzMDZlXHU5ODA2XHUzMDZhXHUzMDZlXHUzMDY3XHUzMGI4XHUzMGIwXHUzMGI2XHUzMGIwXHU2NTcwXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlXHU0ZTAwXHU2NWI5XHVmZjBjMTIzIFx1MzA4NCA3MTQ0NiBcdTMwODQgNzE0NDIgXHUzMDg0IDg4IFx1MzA2Zlx1MzBiOFx1MzBiMFx1MzBiNlx1MzBiMFx1NjU3MFx1MzA2N1x1MzA2Zlx1MzA2YVx1MzA0NFx1ZmYwZVx1MzA2YVx1MzA0YVx1ZmYwYzEgXHU2ODQxXHUzMDZlXHU2YjYzXHUzMDZlXHU2NTc0XHU2NTcwXHUzMDZmXHUzMGI4XHUzMGIwXHUzMGI2XHUzMGIwXHU2NTcwXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDY4XHU4MDAzXHUzMDQ4XHUzMDhiXHUzMDUzXHUzMDY4XHUzMDY4XHUzMDU5XHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPkEgXHU0ZWU1XHU0ZTBhIEIgXHU0ZWU1XHU0ZTBiXHUzMDZlIE0gXHUzMDZlXHU1MDBkXHU2NTcwXHUzMDZlXHUzMDQ2XHUzMDYxXHVmZjBjXHUzMGI4XHUzMGIwXHUzMGI2XHUzMGIwXHU2NTcwXHUzMDZlXHU1MDBiXHU2NTcwXHUzMDkyIDEwMDAwIFx1MzA2N1x1NTI3Mlx1MzA2M1x1MzA1Zlx1NGY1OVx1MzA4YVx1MzA5Mlx1NmM0Mlx1MzA4MVx1MzA4Ylx1MzBkN1x1MzBlZFx1MzBiMFx1MzBlOVx1MzBlMFx1MzA5Mlx1NGY1Y1x1NjIxMFx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHU1MTY1XHU1MjliXHUzMDZmIDMgXHU4ODRjXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhhXHVmZjBjMSBcdTg4NGNcdTMwNmIgMSBcdTMwNjRcdTMwNWFcdTMwNjRcdTZiNjNcdTMwNmVcdTY1NzRcdTY1NzBcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+MSBcdTg4NGNcdTc2ZWVcdTMwNmVcdTY1NzRcdTY1NzBcdTMwNmYgQSBcdTMwOTJcdWZmMGMyIFx1ODg0Y1x1NzZlZVx1MzA2ZVx1NjU3NFx1NjU3MFx1MzA2ZiBCIFx1MzA5Mlx1ZmYwYzMgXHU4ODRjXHU3NmVlXHUzMDZlXHU2NTc0XHU2NTcwXHUzMDZmIE0gXHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlXHUzMDUzXHUzMDhjXHUzMDg5XHUzMDZmIDEgXHUyMjY2IEEgXHUyMjY2IEIgXHUyMjY2IDEwPHN1cD41MDA8XC9zdXA+XHVmZjBjMSBcdTIyNjYgTSBcdTIyNjYgNTAwIFx1MzA5Mlx1NmU4MFx1MzA1Zlx1MzA1OVx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTIwM2IgQSBcdTMwODQgQiBcdTMwNmVcdTUwMjRcdTMwNmZcdWZmMGNcdTkwMWFcdTVlMzhcdTMwNmVcdTY1NzRcdTY1NzBcdTMwOTJcdTg4NjhcdTMwNTlcdTMwYzdcdTMwZmNcdTMwYmZcdTU3OGJcdTMwNmJcdTMwNmZcdTUzY2VcdTMwN2VcdTMwODlcdTMwNmFcdTMwNDRcdTUzZWZcdTgwZmRcdTYwMjdcdTMwNGNcdTMwNDJcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmJcdTZjZThcdTYxMGZcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5BIFx1NGVlNVx1NGUwYSBCIFx1NGVlNVx1NGUwYlx1MzA2ZSBNIFx1MzA2ZVx1NTAwZFx1NjU3MFx1MzA2ZVx1MzA0Nlx1MzA2MVx1ZmYwY1x1MzBiOFx1MzBiMFx1MzBiNlx1MzBiMFx1NjU3MFx1MzA2ZVx1NTAwYlx1NjU3MFx1MzA5MiAxMDAwMCBcdTMwNjdcdTUyNzJcdTMwNjNcdTMwNWZcdTRmNTlcdTMwOGFcdTMwOTIgMSBcdTg4NGNcdTMwNjdcdTUxZmFcdTUyOWJcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNzdjXHViY2Y4XHVjNWI0In1d