시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB126413338.824%

문제

양의 정수의 각 자리의 변화가 증가와 감소를 번갈아가면서 나타날 때, 이 숫자를 "지그재그 수"라고 한다. 예를 들어, 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

예제 입력 2

6
1234567
3

예제 출력 2

246
W3sicHJvYmxlbV9pZCI6IjU1NDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjggXHVjMjJiXHVjNzkwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzU4IFx1YWMwMSBcdWM3OTBcdWI5YWNcdWM3NTggXHViY2MwXHVkNjU0XHVhYzAwIFx1Yzk5ZFx1YWMwMFx1YzY0MCBcdWFjMTBcdWMxOGNcdWI5N2MgXHViYzg4XHVhYzA4XHVjNTQ0XHVhYzAwXHViYTc0XHVjMTFjIFx1YjA5OFx1ZDBjMFx1YjBhMCBcdWI1NGMsIFx1Yzc3NCBcdWMyMmJcdWM3OTBcdWI5N2MgJnF1b3Q7XHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzIxOCZxdW90O1x1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIDI5NDdcdWM3NDAgXHVjNzkwXHViOWFjXHVhYzAwIDImcmFycjs5JnJhcnI7NCZyYXJyOzdcdWI4NWMgXHVjOTlkXHVhYzAwJnJhcnI7XHVhYzEwXHVjMThjJnJhcnI7XHVjOTlkXHVhYzAwIFx1YzIxY1x1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViNjEwLCA3MTk0Nlx1Yzc0MCBcdWFjMTBcdWMxOGMmcmFycjtcdWM5OWRcdWFjMDAmcmFycjtcdWFjMTBcdWMxOGMmcmFycjtcdWM5OWRcdWFjMDBcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzljMFx1YWRmOFx1YzdhY1x1YWRmOCBcdWMyMThcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgMTIzLCA3MTQ0NiwgNzE0NDIsIDg4XHVjNzQwIFx1YzljMFx1YWRmOFx1YzdhY1x1YWRmOCBcdWMyMThcdWFjMDAgXHVjNTQ0XHViMmM4XHViMmU0LiBcdWQ1NWMgXHVjNzkwXHViOWFjIFx1YzgxNVx1YzIxOFx1YjI5NCBcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjggXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5BXHVjNzc0XHVjMGMxIEJcdWM3NzRcdWQ1NThcdWM3NTggTVx1Yzc1OCBcdWJjMzBcdWMyMTggXHVjOTExIFx1YzljMFx1YWRmOFx1YzdhY1x1YWRmOCBcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBBLCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIEIsIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDAgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQSAmbGU7IEIgJmxlOyAxMDxzdXA+NTAwPFwvc3VwPiwgMSAmbGU7IE0gJmxlOyA1MDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+QVx1Yzc3NFx1YzBjMSBCXHVjNzc0XHVkNTU4XHVjNzU4IE1cdWM3NTggXHViYzMwXHVjMjE4IFx1YzkxMSBcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjggXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyAxMDAwMFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+MTA1LCAxMjAsIDEzMCwgMTQwLCAxNTAsIDE2MCwgMTY1LCAxNzAsIDE3NSwgMTgwLCAxODUsIDE5MCwgMTk1PFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiNTU0OCIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6Ilx1MzBiOFx1MzBiMFx1MzBiNlx1MzBiMFx1NjU3MCAoWmlnLVphZyBOdW1iZXJzKSIsImRlc2NyaXB0aW9uIjoiPHA+XHU2YjYzXHUzMDZlXHU2NTc0XHU2NTcwXHUzMDkyIChcdTUxNDhcdTk4MmRcdTMwNmIgMCBcdTMwOTJcdTMwNjRcdTMwNTFcdTMwNWFcdTMwNmIpIDEwIFx1OTAzMlx1NmNkNVx1MzA2N1x1NjZmOFx1MzA0NFx1MzA2Nlx1Njg0MVx1MzA2ZVx1NjU3MFx1NWI1N1x1MzA5Mlx1OTgwNlx1NzU2YVx1MzA2Ylx1ODk4Ylx1MzA2Nlx1MzA0NFx1MzA0Zlx1MzA2OFx1NTg5N1x1NTJhMFx1MzA2OFx1NmUxYlx1NWMxMVx1MzA5Mlx1NGVhNFx1NGU5Mlx1MzA2Ylx1N2U3MFx1MzA4YVx1OGZkNFx1MzA1N1x1MzA2Nlx1MzA0NFx1MzA4Ylx1MzA2OFx1MzA0ZFx1ZmYwY1x1MzA1ZFx1MzA2ZVx1NjU3MFx1MzA2Zlx1MzAwY1x1MzBiOFx1MzBiMFx1MzBiNlx1MzBiMFx1NjU3MFx1MzAwZFx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA2OFx1NTQ3Y1x1MzA3Nlx1MzA1M1x1MzA2OFx1MzA2Ylx1MzA1N1x1MzA4OFx1MzA0Nlx1ZmYwZVx1MzA1Zlx1MzA2OFx1MzA0OFx1MzA3MFx1ZmYwYzI5NDcgXHUzMDZmXHU2ODQxXHUzMDZlXHU2NTcwXHU1YjU3XHUzMDRjIDIgJnJhcnI7IDkgJnJhcnI7IDQgJnJhcnI7IDcgXHUzMDY4XHVmZjBjXHU1ODk3XHU1MmEwICZyYXJyOyBcdTZlMWJcdTVjMTEgJnJhcnI7IFx1NTg5N1x1NTJhMCBcdTMwNmVcdTk4MDZcdTMwNmJcdTMwNmFcdTMwNjNcdTMwNjZcdTMwNDRcdTMwOGJcdTMwNmVcdTMwNjdcdTMwYjhcdTMwYjBcdTMwYjZcdTMwYjBcdTY1NzBcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGVcdTMwN2VcdTMwNWZcdWZmMGM3MTk0NiBcdTMwNmYgXHU2ZTFiXHU1YzExICZyYXJyOyBcdTU4OTdcdTUyYTAgJnJhcnI7IFx1NmUxYlx1NWMxMSAmcmFycjsgXHU1ODk3XHU1MmEwIFx1MzA2ZVx1OTgwNlx1MzA2YVx1MzA2ZVx1MzA2N1x1MzBiOFx1MzBiMFx1MzBiNlx1MzBiMFx1NjU3MFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZVx1NGUwMFx1NjViOVx1ZmYwYzEyMyBcdTMwODQgNzE0NDYgXHUzMDg0IDcxNDQyIFx1MzA4NCA4OCBcdTMwNmZcdTMwYjhcdTMwYjBcdTMwYjZcdTMwYjBcdTY1NzBcdTMwNjdcdTMwNmZcdTMwNmFcdTMwNDRcdWZmMGVcdTMwNmFcdTMwNGFcdWZmMGMxIFx1Njg0MVx1MzA2ZVx1NmI2M1x1MzA2ZVx1NjU3NFx1NjU3MFx1MzA2Zlx1MzBiOFx1MzBiMFx1MzBiNlx1MzBiMFx1NjU3MFx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA2OFx1ODAwM1x1MzA0OFx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2OFx1MzA1OVx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD5BIFx1NGVlNVx1NGUwYSBCIFx1NGVlNVx1NGUwYlx1MzA2ZSBNIFx1MzA2ZVx1NTAwZFx1NjU3MFx1MzA2ZVx1MzA0Nlx1MzA2MVx1ZmYwY1x1MzBiOFx1MzBiMFx1MzBiNlx1MzBiMFx1NjU3MFx1MzA2ZVx1NTAwYlx1NjU3MFx1MzA5MiAxMDAwMCBcdTMwNjdcdTUyNzJcdTMwNjNcdTMwNWZcdTRmNTlcdTMwOGFcdTMwOTJcdTZjNDJcdTMwODFcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1NTE2NVx1NTI5Ylx1MzA2ZiAzIFx1ODg0Y1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4YVx1ZmYwYzEgXHU4ODRjXHUzMDZiIDEgXHUzMDY0XHUzMDVhXHUzMDY0XHU2YjYzXHUzMDZlXHU2NTc0XHU2NTcwXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPjEgXHU4ODRjXHU3NmVlXHUzMDZlXHU2NTc0XHU2NTcwXHUzMDZmIEEgXHUzMDkyXHVmZjBjMiBcdTg4NGNcdTc2ZWVcdTMwNmVcdTY1NzRcdTY1NzBcdTMwNmYgQiBcdTMwOTJcdWZmMGMzIFx1ODg0Y1x1NzZlZVx1MzA2ZVx1NjU3NFx1NjU3MFx1MzA2ZiBNIFx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZVx1MzA1M1x1MzA4Y1x1MzA4OVx1MzA2ZiAxIFx1MjI2NiBBIFx1MjI2NiBCIFx1MjI2NiAxMDxzdXA+NTAwPFwvc3VwPlx1ZmYwYzEgXHUyMjY2IE0gXHUyMjY2IDUwMCBcdTMwOTJcdTZlODBcdTMwNWZcdTMwNTlcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHUyMDNiIEEgXHUzMDg0IEIgXHUzMDZlXHU1MDI0XHUzMDZmXHVmZjBjXHU5MDFhXHU1ZTM4XHUzMDZlXHU2NTc0XHU2NTcwXHUzMDkyXHU4ODY4XHUzMDU5XHUzMGM3XHUzMGZjXHUzMGJmXHU1NzhiXHUzMDZiXHUzMDZmXHU1M2NlXHUzMDdlXHUzMDg5XHUzMDZhXHUzMDQ0XHU1M2VmXHU4MGZkXHU2MDI3XHUzMDRjXHUzMDQyXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZiXHU2Y2U4XHU2MTBmXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+QSBcdTRlZTVcdTRlMGEgQiBcdTRlZTVcdTRlMGJcdTMwNmUgTSBcdTMwNmVcdTUwMGRcdTY1NzBcdTMwNmVcdTMwNDZcdTMwNjFcdWZmMGNcdTMwYjhcdTMwYjBcdTMwYjZcdTMwYjBcdTY1NzBcdTMwNmVcdTUwMGJcdTY1NzBcdTMwOTIgMTAwMDAgXHUzMDY3XHU1MjcyXHUzMDYzXHUzMDVmXHU0ZjU5XHUzMDhhXHUzMDkyIDEgXHU4ODRjXHUzMDY3XHU1MWZhXHU1MjliXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaGludCI6IjxwPlx1NTE2NVx1NTFmYVx1NTI5Ylx1NGY4YiAxIFx1MzA2Ylx1MzA0YVx1MzA0NFx1MzA2Nlx1ZmYwYzEwMCBcdTRlZTVcdTRlMGEgMjAwIFx1NGVlNVx1NGUwYlx1MzA2ZSA1IFx1MzA2ZVx1NTAwZFx1NjU3MFx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzBiOFx1MzBiMFx1MzBiNlx1MzBiMFx1NjU3MFx1MzA2Zlx1ZmYwYzEwNSwgMTIwLCAxMzAsIDE0MCwgMTUwLCAxNjAsIDE2NSwgMTcwLCAxNzUsIDE4MCwgMTg1LCAxOTAsIDE5NSBcdTMwNmUgMTMgXHU1MDBiXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NTE2NVx1NTFmYVx1NTI5Ylx1NGY4YiAyIFx1MzA2Ylx1MzA0YVx1MzA0NFx1MzA2Nlx1ZmYwYzYgXHU0ZWU1XHU0ZTBhIDEyMzQ1NjcgXHU0ZWU1XHU0ZTBiXHUzMDZlIDMgXHUzMDZlXHU1MDBkXHU2NTcwXHUzMDY3XHUzMDQyXHUzMDhiXHUzMGI4XHUzMGIwXHUzMGI2XHUzMGIwXHU2NTcwXHUzMDZmIDUwMjQ2IFx1NTAwYlx1MzA0Mlx1MzA4Ylx1MzA2ZVx1MzA2N1x1ZmYwY1x1MzA1ZFx1MzA4Y1x1MzA5MiAxMDAwMCBcdTMwNjdcdTUyNzJcdTMwNjNcdTMwNWZcdTRmNTlcdTMwOGFcdTMwNjdcdTMwNDJcdTMwOGIgMjQ2IFx1MzA5Mlx1NTFmYVx1NTI5Ylx1MzA1OVx1MzA4Ylx1ZmYwZTxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiSmFwYW5lc2UifV0=