시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 47 15 14 34.146%

문제

이 문제에서 자연수 하나를 숫자들의 수열로 나타낼 수 있다고 한다. 마찬가지로 숫자로 이루어진 수열을 자연수 하나로 표현할 수 있다. 하지만 leading zeros (맨 앞의 0)은 허용하지 않는다. 예를 들어 N = 2090 일 때, 수열 {2, 0, 9, 0}이 된다. 하지만 수열 {0, 0, 1, 0}이 의미하는 자연수는 없다.

수열의 Anagram이란 수열의 원소 구성은 같으면서 순서만 바뀐 것을 의미한다. 마찬가지로 자연수의 Anagram도 정의할 수 있다. N = 2090 일 때, N의 Anagram은 2009, 2090, 2900, 9002, 9020, 9200이 된다.

자연수 N이 주어졌을 때, N의 Anagram 중 11의 배수가 되는 것이 몇 개나 있는지 궁금하다. 이를 계산하는 프로그램을 작성하자. 예를 들어, N = 2090 일 때 Anagram 중 2090 과 9020 만이 11의 배수이기 때문에 답은 2가 된다.

입력

첫 줄에 자연수 N이 leading zeros 없이 주어진다. (1 ≤ N ≤ 10100)

출력

주어진 자연수 N의 Anagram 중 11의 배수의 개수를 출력한다. 단, 답이 매우 클 수 있으므로 109 + 7로 나눈 나머지를 출력한다.

예제 입력 1

2090

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6Ijk1MjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiIxMSAoXHVjMmVkIFx1Yzc3YykiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVjNzkwXHVjNWYwXHVjMjE4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWMyMmJcdWM3OTBcdWI0ZTRcdWM3NTggXHVjMjE4XHVjNWY0XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViOWM4XHVjYzJjXHVhYzAwXHVjOWMwXHViODVjIFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Yzc5MFx1YzVmMFx1YzIxOCBcdWQ1NThcdWIwOThcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBsZWFkaW5nIHplcm9zIChcdWI5ZTggXHVjNTVlXHVjNzU4IDApXHVjNzQwIFx1ZDVjOFx1YzZhOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuJm5ic3A7XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBOID0gMjA5MCBcdWM3N2MgXHViNTRjLCBcdWMyMThcdWM1ZjQgezIsIDAsIDksIDB9XHVjNzc0IFx1YjQxY1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YzIxOFx1YzVmNCZuYnNwO3swLCAwLCAxLCAwfVx1Yzc3NCBcdWM3NThcdWJiZjhcdWQ1NThcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4XHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMjE4XHVjNWY0XHVjNzU4Jm5ic3A7QW5hZ3JhbVx1Yzc3NFx1Yjc4MCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjNmQwXHVjMThjIFx1YWQ2Y1x1YzEzMVx1Yzc0MCBcdWFjMTlcdWM3M2NcdWJhNzRcdWMxMWMgXHVjMjFjXHVjMTFjXHViOWNjIFx1YmMxNFx1YjAxMCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWI5YzhcdWNjMmNcdWFjMDBcdWM5YzBcdWI4NWMgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzU4IEFuYWdyYW1cdWIzYzQgXHVjODE1XHVjNzU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIE4gPSAyMDkwJm5ic3A7XHVjNzdjIFx1YjU0YywgTlx1Yzc1OCBBbmFncmFtXHVjNzQwIDIwMDksIDIwOTAsIDI5MDAsIDkwMDIsIDkwMjAsIDkyMDBcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3OTBcdWM1ZjBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBOXHVjNzU4IEFuYWdyYW0gXHVjOTExIDExXHVjNzU4IFx1YmMzMFx1YzIxOFx1YWMwMCBcdWI0MThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmE4NyBcdWFjMWNcdWIwOTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ4MVx1YWUwOFx1ZDU1OFx1YjJlNC4gXHVjNzc0XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjNzkwLiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBOID0gMjA5MCBcdWM3N2MgXHViNTRjIEFuYWdyYW0gXHVjOTExIDIwOTAgXHVhY2ZjIDkwMjAgXHViOWNjXHVjNzc0IDExXHVjNzU4IFx1YmMzMFx1YzIxOFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViMmY1XHVjNzQwIDJcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWM3OTBcdWM1ZjBcdWMyMTggTlx1Yzc3NCBsZWFkaW5nIHplcm9zIFx1YzVjNlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiZuYnNwOyZsZTsgMTA8c3VwPjEwMDxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1Yzc5MFx1YzVmMFx1YzIxOCBOXHVjNzU4IEFuYWdyYW0gXHVjOTExIDExXHVjNzU4IFx1YmMzMFx1YzIxOFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZTgsIFx1YjJmNVx1Yzc3NCBcdWI5ZTRcdWM2YjAgXHVkMDc0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMgMTA8c3VwPjk8XC9zdXA+ICsgN1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5NTI5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRWxldmVuIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGlzIHByb2JsZW0sIHdlIHJlZmVyIHRvIHRoZSBkaWdpdHMgb2YgYSBwb3NpdGl2ZSBpbnRlZ2VyIGFzIHRoZSBzZXF1ZW5jZSBvZiBkaWdpdHMgcmVxdWlyZWQgdG8gd3JpdGUgaXQgaW4gYmFzZSAxMCB3aXRob3V0IGxlYWRpbmcgemVyb3MuIEZvciBpbnN0YW5jZSwgdGhlIGRpZ2l0cyBvZiBOID0gMjA5MCBhcmUgb2YgY291cnNlIDIsIDAsIDkgYW5kIDAuPFwvcD5cclxuXHJcbjxwPkxldCBOIGJlIGEgcG9zaXRpdmUgaW50ZWdlci4gV2UgY2FsbCBhIHBvc2l0aXZlIGludGVnZXIgTSBhbiBlbGV2ZW4tbXVsdGlwbGUtYW5hZ3JhbSBvZiBOIGlmIGFuZCBvbmx5IGlmICgxKSB0aGUgZGlnaXRzIG9mIE0gYXJlIGEgcGVybXV0YXRpb24gb2YgdGhlIGRpZ2l0cyBvZiBOLCBhbmQgKDIpIE0gaXMgYSBtdWx0aXBsZSBvZiAxMS4gWW91IGFyZSByZXF1aXJlZCB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBnaXZlbiBOLCBjYWxjdWxhdGVzIHRoZSBudW1iZXIgb2YgaXRzIGVsZXZlbi1tdWx0aXBsZS1hbmFncmFtcy48XC9wPlxyXG5cclxuPHA+QXMgYW4gZXhhbXBsZSwgY29uc2lkZXIgYWdhaW4gTiA9IDIwOTAuIFRoZSB2YWx1ZXMgdGhhdCBtZWV0IHRoZSBmaXJzdCBjb25kaXRpb24gYWJvdmUgYXJlIDIwMDksIDIwOTAsIDI5MDAsIDkwMDIsIDkwMjAgYW5kIDkyMDAuIEFtb25nIHRob3NlLCBvbmx5IDIwOTAgYW5kIDkwMjAgc2F0aXNmeSB0aGUgc2Vjb25kIGNvbmRpdGlvbiwgc28gdGhlIGFuc3dlciBmb3IgTiA9IDIwOTAgaXMgMi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkEgc2luZ2xlIGxpbmUgdGhhdCBjb250YWlucyBhbiBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTA8c3VwPjEwMDxcL3N1cD4pLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBhIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIGVsZXZlbi1tdWx0aXBsZS1hbmFncmFtcyBvZiBOLiBCZWNhdXNlIHRoaXMgbnVtYmVyIGNhbiBiZSB2ZXJ5IGxhcmdlLCB5b3UgYXJlIHJlcXVpcmVkIHRvIG91dHB1dCB0aGUgcmVtYWluZGVyIG9mIGRpdmlkaW5nIGl0IGJ5IDEwPHN1cD45PFwvc3VwPiArIDcuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d