시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1 1 1 100.000%

문제

호그볼트 수리마법과에 재학중인 서녕미온느는 올해 학교를 졸업한다. 상근 포터는 서녕미온느를 매우 심하게 괴롭혔고, 서녕미온느는 졸업을 하기 전에 상근 포터의 컴퓨터를 해킹하려고 한다.

상근 포터의 비밀번호는 1부터 N까지 자연수로 이루어진 순열이다. 상근 포터는 자연수 K에 집착한다. 예를 들어, 처음 보는 사람을 만났을 때, 그는 그 사람에게 자기 이름을 K번 말한다. 서녕미온느는 상근 포터가 비밀번호 치는 장면을 대학 재학동안 꾸준히 봤고, 그의 비밀번호의 순서는 K라는 사실을 알게되었다.

x ∈ {1, ..., N}의 모든 x를 상근 포터의 비밀번호에서 x가 있는 위치의 수로 K번 바꿨을 때, 다시 원래 x로 돌아오는 가장 작은 K를 순열의 순서라고 한다. 예를 들어, 순열이 2 3 1인 경우 1 → 3 → 2 → 1, 2 → 1 → 3 → 2, 3 → 2 → 1 → 3이기 때문에, 순열의 순서는 3이다.

N과 K가 주어졌을 때, 상근이의 비밀번호로 가능한 순열의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 100, 1 ≤ K ≤ 231 - 1)

출력

1부터 N까지 숫자로 이루어진 순열 중 순서가 K인 것의 개수를 231 - 1로 나눈 나머지를 출력한다. 

예제 입력 1

15 12

예제 출력 1

1789014075

힌트

W3sicHJvYmxlbV9pZCI6IjUwNDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2MzhcdWFkZjhcdWJjZmNcdWQyYjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDYzOFx1YWRmOFx1YmNmY1x1ZDJiOCBcdWMyMThcdWI5YWNcdWI5YzhcdWJjOTVcdWFjZmNcdWM1ZDAgXHVjN2FjXHVkNTU5XHVjOTExXHVjNzc4IFx1YzExY1x1YjE1NVx1YmJmOFx1YzYyOFx1YjI5MFx1YjI5NCBcdWM2MmNcdWQ1NzQgXHVkNTU5XHVhZDUwXHViOTdjIFx1Yzg3OFx1YzVjNVx1ZDU1Y1x1YjJlNC4gXHVjMGMxXHVhZGZjIFx1ZDNlY1x1ZDEzMFx1YjI5NCBcdWMxMWNcdWIxNTVcdWJiZjhcdWM2MjhcdWIyOTBcdWI5N2MgXHViOWU0XHVjNmIwIFx1YzJlY1x1ZDU1OFx1YWM4YyBcdWFkMzRcdWI4NmRcdWQ2MTRcdWFjZTAsIFx1YzExY1x1YjE1NVx1YmJmOFx1YzYyOFx1YjI5MFx1YjI5NCBcdWM4NzhcdWM1YzVcdWM3NDQgXHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWMwYzFcdWFkZmMgXHVkM2VjXHVkMTMwXHVjNzU4IFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yjk3YyBcdWQ1NzRcdWQwYjlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmMgXHVkM2VjXHVkMTMwXHVjNzU4IFx1YmU0NFx1YmMwMFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHVjNzkwXHVjNWYwXHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMWNcdWM1ZjRcdWM3NzRcdWIyZTQuIFx1YzBjMVx1YWRmYyBcdWQzZWNcdWQxMzBcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4IEtcdWM1ZDAgXHVjOWQxXHVjYzI5XHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWNjOThcdWM3NGMgXHViY2Y0XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc0NCBcdWI5Y2NcdWIwYWNcdWM3NDQgXHViNTRjLCBcdWFkZjhcdWIyOTQgXHVhZGY4IFx1YzBhY1x1Yjc4Y1x1YzVkMFx1YWM4YyBcdWM3OTBcdWFlMzAgXHVjNzc0XHViOTg0XHVjNzQ0IEtcdWJjODggXHViOWQwXHVkNTVjXHViMmU0LiBcdWMxMWNcdWIxNTVcdWJiZjhcdWM2MjhcdWIyOTBcdWIyOTQgXHVjMGMxXHVhZGZjIFx1ZDNlY1x1ZDEzMFx1YWMwMCBcdWJlNDRcdWJjMDBcdWJjODhcdWQ2MzggXHVjZTU4XHViMjk0IFx1YzdhNVx1YmE3NFx1Yzc0NCBcdWIzMDBcdWQ1NTkgXHVjN2FjXHVkNTU5XHViM2Q5XHVjNTQ4IFx1YWZiOFx1YzkwMFx1ZDc4OCBcdWJkMjRcdWFjZTAsIFx1YWRmOFx1Yzc1OCBcdWJlNDRcdWJjMDBcdWJjODhcdWQ2MzhcdWM3NTggXHVjMjFjXHVjMTFjXHViMjk0IEtcdWI3N2NcdWIyOTQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YzU0Y1x1YWM4Y1x1YjQxOFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+eCAmaXNpbjsgezEsIC4uLiwgTn1cdWM3NTggXHViYWE4XHViNGUwIHhcdWI5N2MgXHVjMGMxXHVhZGZjIFx1ZDNlY1x1ZDEzMFx1Yzc1OCBcdWJlNDRcdWJjMDBcdWJjODhcdWQ2MzhcdWM1ZDBcdWMxMWMgeFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVjNzA0XHVjZTU4XHVjNzU4IFx1YzIxOFx1Yjg1YyBLXHViYzg4IFx1YmMxNFx1YWZlOFx1Yzc0NCBcdWI1NGMsIFx1YjJlNFx1YzJkYyBcdWM2ZDBcdWI3OTggeFx1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWIyOTQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBLXHViOTdjIFx1YzIxY1x1YzVmNFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWMyMWNcdWM1ZjRcdWM3NzQgMiAzIDFcdWM3NzggXHVhY2JkXHVjNmIwIDEgJnJhcnI7IDMgJnJhcnI7IDIgJnJhcnI7IDEsIDIgJnJhcnI7IDEgJnJhcnI7IDMgJnJhcnI7IDIsIDMgJnJhcnI7IDIgJnJhcnI7IDEgJnJhcnI7IDNcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWMyMWNcdWM1ZjRcdWM3NTggXHVjMjFjXHVjMTFjXHViMjk0IDNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjZmMgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHViZTQ0XHViYzAwXHViYzg4XHVkNjM4XHViODVjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWMyMWNcdWM1ZjRcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAsIDEgJmxlOyBLICZsZTsgMjxzdXA+MzE8XC9zdXA+IC0gMSk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4xXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHVjMjJiXHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMWNcdWM1ZjQgXHVjOTExIFx1YzIxY1x1YzExY1x1YWMwMCBLXHVjNzc4IFx1YWM4M1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgMjxzdXA+MzE8XC9zdXA+IC0gMVx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1MDQxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ29kZSBQZXJtdXRhdGlvbnMiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgc29vbiB0byBncmFkdWF0ZSBmcm9tIHRoZSBtYXRoZW1hZ2ljaWFuIHNjaG9vbCBvZiBIYWd3b3J0cywgYW5kIHlvdSYjMzk7cmUgcXVpdGUgY29udGVudCB3aXRoIHlvdXJzZWxmOyBhbGwgdGhlIGhhcmQgd29yayBhbmQgZWxib3dpbmcgaGFzIGZpbmFsbHkgcGFpZCBvZmYuIEJlaW5nIHN1Y2Nlc3NmdWwgYXQgbW9zdCBvZiB5b3UgZW5kZWF2b3JzIHlvdSB3b3VsZCBub3JtYWxseSBlbmQgdXAgYSBoZXJhbGQgb2Ygc291bmQgcmVhc29uaW5nIGFuZCBnb29kIG1hdGhlbWFnaWNzLiBZb3UsIGhvd2V2ZXIsIGFyZSBkaWZmZXJlbnQ7IG5vdCBvbmx5IGhhdmUgeW91IHNwZW50IHlvdXIgeW91bmcgeWVhcnMgc2VjcmV0bHkgaGFja2luZyBhd2F5IGF0IGNvbXB1dGVycywgd3JpdGluZyBjb2RlIHRvIGRvIHlvdXIgYXNzaWduZWQgcm91dGluZSBob21ld29yayBmb3IgeW91LCBidXQgb2YgbGF0ZSB5b3UgaGF2ZSBzdGFydGVkIHBsYW5uaW5nIGhvdyB0byBjcmFtIGFsbCB5b3VyIG1hdGhlbWFnaWNhbCBza2lsbHMgaW50byBhIGNvbXB1dGVyIHRvIGNvbXBsZXRlbHkgZWxpbWluYXRlIHRoZSBuZWVkIGZvciBtYXRoZW1hZ2ljaWFucyEgVG8gc2hvdyB0aGUgb3RoZXJzIGp1c3QgaG93IGdyZWF0IGEgdmlzaW9uYXJ5IHlvdSBhcmUsIHlvdSBwbGFuIHRvIG1ha2UgeW91ciBncmFkdWF0aW9uIGNlcmVtb255IHNvbWV0aGluZyB0aGV5IHdpbGwgbmV2ZXIgZm9yZ2V0LjxcL3A+XHJcblxyXG48cD5UbyBkbyB0aGlzIHlvdSBuZWVkIHRvIGJyZWFrIGludG8gdGhlIHNhZmUgb2YgeW91ciBhcmNoLW5lbWVzaXMsIEhhaXJ5IFBldGVyLiBUaGUgc2FmZSBpcyBsb2NrZWQgYnkgYSBjb2RlIG1lY2hhbmlzbTogQWxsIG5hdHVyYWwgbnVtYmVycyBmcm9tIDEgdG8gTiBuZWVkIHRvIGJlIHR5cGVkIGluIGluIHRoZSBjb3JyZWN0IG9yZGVyLCBzZXQgYnkgSGFpcnkgUGV0ZXIuIEZvcnR1bmF0ZWx5IHlvdSBrbm93IHRoYXQgSGFpcnksIGJlaW5nIGEgZ29vZCBtYXRoZW1hZ2ljaWFuLCBoYXMgYSBjZXJ0YWluIHdlYWtuZXNzOyBoZSBoYXMgYSByYXRoZXIgdW5oZWFsdGh5IG9ic2Vzc2lvbiB3aXRoIHRoZSBudW1iZXIgSy4gKEZvciBpbnN0YW5jZSBoZSBhbHdheXMgaGFzIHRvIGludHJvZHVjZSBoaW1zZWxmIEsgdGltZXMgd2hlbmV2ZXIgaGUgbWVldHMgbmV3IHBlb3BsZSwgbWFraW5nIGhpbSBxdWl0ZSBhbm5veWluZyB0byBiZSBhcm91bmQuKSBUaHVzIHlvdSBhcmUgY2VydGFpbiB0aGF0IGhpcyBjb2RlLCB3aGVuIHZpZXdlZCBhcyBhIHBlcm11dGF0aW9uIG9mIHRoZSBOIGZpcnN0IG5hdHVyYWxzLCBoYXMgb3JkZXIgZXhhY3RseSBLLiAoaS5lLiBLIGlzIHRoZSBzbWFsbGVzdCBwb3NpdGl2ZSBudW1iZXIgc3VjaCB0aGF0IGlmIHlvdSBLIHRpbWVzIHJlcGxhY2UgeCAmaXNpbjsgezEsIC4uLiwgTn0gd2l0aCB0aGUgcG9zaXRpb24gb2YgeCBpbiBIYWlyeSYjMzk7cyBjb2RlLCB5b3UgZW5kIHVwIHdpdGggdGhlIHggeW91IHN0YXJ0ZWQgd2l0aCwgZm9yIGFsbCB4LiBUaHVzIGUuZy4gdGhlIG9yZGVyIG9mIHRoZSBwZXJtdXRhdGlvbiBjb3JyZXNwb25kaW5nIHRvIHRoZSBjb2RlIDIgMyAxIGlzIDMsIGFzIDEgJnJhcnI7IDMgJnJhcnI7IDIgJnJhcnI7IDEgYW5kIDIgJnJhcnI7IDEgJnJhcnI7IDMgJnJhcnI7IDIgYW5kIDMgJnJhcnI7IDIgJnJhcnI7IDEgJnJhcnI7IDMuKSBXaGlsZSB0aGlzIGRvZXMgbm90IGhlbHAgeW91IGRpcmVjdGx5LCBpdCBncmVhdGx5IHJlZHVjZXMgdGhlIG51bWJlciBvZiBjb2RlIGlucHV0cyB5b3UgbWF5IGhhdmUgdG8gdHJ5IGJlZm9yZSB5b3UgZmluZCB0aGUgY29ycmVjdCBvbmUuICZxdW90O0hvdyBtYW55PyZxdW90OyBpcyB0aGUgcXVlc3Rpb24geW91IGFyZSBwb25kZXJpbmcgcmlnaHQgbm93LiBZb3UgbXVzdCBrbm93IHRoZSBleGFjdCBudW1iZXIsIGxlc3QgeW91IHJpc2sgcHJlcGFyaW5nIHRvbyBsaXR0bGUgdGltZSBmb3IgY3JhY2tpbmcgdGhlIHNhZmUuPFwvcD5cclxuXHJcbjxwPk5vdyB5b3UgYWxzbyBoYXZlIGEgY2VydGFpbiBtYXRoZW1hZ2ljYWwgd2Vha25lc3MgYXJndWFibHkgYSBiaXQgd29yc2UgdGhhbiBIYWlyeSBQZXRlciYjMzk7czogQmVjYXVzZSBvZiB5b3VyIGRhcmsgc2NoZW1lIHRvIHByb2dyYW0gbWF0aGVtYWdpY2FsIGNvbXB1dGVycywgeW91IGluc2lzdCB0aGVyZSBhcmUgbm8gbnVtYmVycyBncmVhdGVyIHRoYW4gd2hhdCBjYW4gYmUgcmVwcmVzZW50ZWQgYnkgYSBzaWduZWQgMzItYml0IGludGVnZXIsIG5hbWVseSB0aGUgcHJpbWUgUCA9IDI8c3VwPjMxPFwvc3VwPiAtIDEuT2YgY291cnNlIHRoZXJlIG11c3QgYmUgbm90aGluZyB5b3VyIGNvbXB1dGVycyBjYW5ub3QgY291bnQuIEluIGZhY3QgeW91IGhhdGUgdGhpcyB1cHBlciBsaW1pdCBQIHNvIGludGVuc2VseSB0aGF0IHlvdSBoYXZlIGRlY2lkZWQgdG8gbWFrZSBhIG5ldyBtYXRoZW1hZ2ljcyB3aGVyZSBQIGVxdWFscyAwLiBIYSwgdGFrZSB0aGF0ISAoV2VsbCwgeW91IGFyZSBxdWl0ZSBhd2FyZSB0aGF0IHlvdSBhcmUgcmVhbGx5IGp1c3QgY291bnRpbmcgbW9kdWxvIFAsIGJ1dCBpdCB3aWxsIGhhdmUgdG8gc3VmZmljZSB1bnRpbCB5b3UgZmluZCBiZXR0ZXIgd2F5cyBvZiBwdW5pc2hpbmcgUC4pIEluIGZhY3QgdGhpcyB0dXJucyBvdXQgdG8gYmUgcXVpdGUgYW4gYWR2YW50YWdlIGZvciB5b3UhIEZvciBpbnN0YW5jZSwgaWYgdGhlIG51bWJlciBvZiBjb2RlIHBlcm11dGF0aW9ucyB5b3UgaGF2ZSB0byBjaGVjayB0dXJucyBvdXQgdG8gYmUgMjxzdXA+MzE8XC9zdXA+LCB0aGVyZSB3aWxsIGFjdHVhbGx5IGJlIGp1c3Qgb25lIHBlcm11dGF0aW9uIGZvciB5b3UgdG8gY2hlY2ssIGFzIDI8c3VwPjMxPFwvc3VwPiBtb2QgUCA9IDEuIChPciBhdCBsZWFzdCB5b3UgdGhpbmsgc28uLi4pIFRoYXQmIzM5O3MganVzdCBtYWduaWZpY2VudCE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiB0d28gaW50ZWdlcnMgTiAoMSAmbGU7IE4gJmxlOyAxMDApIGFuZCBLICgxICZsZTsgSyAmbGU7IDI8c3VwPjMxPFwvc3VwPiAtIDEpIHJlc3BlY3RpdmVseS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgbnVtYmVyIG9mIHBlcm11dGF0aW9ucyBvZiBOIGVsZW1lbnRzIG9mIG9yZGVyIEssIG1vZHVsbyAyPHN1cD4zMTxcL3N1cD4gLSAxLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==