Informatica Online Judge

  거저 먹기 [1293 / 050D]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 13   Total Tried : 86


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (32nd 오선재)]

Background

koistudy.net 이라는 페이지에는 “과자먹기”라는 문제가 있는데 이 문제는 매우 어려워서 그 풀이를 알고 있는 사람이 별로 없다고 한다.

(참고: 과자먹기 : 과자 먹기)

그러나 “Mr. Koo”는 풀 문제가 너무 없는 나머지 “과자먹기”를 풀려고 하였다. 그래서 Mr. Koo는 과자먹기의 챔피언 “Mr. GG”에게 코드를 얻어보려고 한다. 그러나 Mr. GG는 한 가지의 조건을 걸었다.

1. K-G-블럭을 K-블럭에서 돌리거나 뒤집어 모양이 같아지는 경우도 다른 가짓수로 세며, 단 K-G-블럭의 모든 변이 바닥과 수직하거나 평행하기만 하면 되는 블럭으로 정의한다.

다음은 5-블럭에 대한 예이다.



단, 돌리거나 뒤집지 않아도 모양이 같아지는 두 블럭은 같은 블럭이다.

예를 들어, 3-G 블럭은 다음과 같이 6가지가 존재한다.

ㅁㅁㅁ






ㅁㅁ

ㅁㅁ


ㅁㅁ



ㅁㅁ


2. K-G-블럭에서 ‘정사각형을 점, 정사각형끼리 연결된 변을 선으로 하는 그래프’에서 해밀턴 경로의 개수를 모두 구하면 코드를 줄 것이다. 단 개수가 너무 클 경우엔 M으로 나눈 나머지를 구하여라

이 문제만 풀면 한 문제를 거저먹을 수 있다는 생각에 Mr. Koo는 열심히 문제를 풀고 있다. 여러분이 Mr. Koo를 도와주자.

Input

첫째 줄에 K가 주어진다. 2<=K<=13 이며 K는 자연수이다.
둘째 줄에 M이 주어진다. 1<=M<=10^16이며 M은 자연수이다.

Output

모든 K-G-블럭에서 나올 수 있는 각각의 해밀턴 경로의 가짓수의 합을 M으로 나눈 나머지를 한 줄에 출력한다.

단, 어떤 K-G-블럭에서는 해밀턴 경로가 없을 수도 있는데 이것은 0가지로 계산한다.

또한, 초기 K-G-블럭의 각 정사각형에 번호를 매겼을 때, 시작점에서 도착점으로 가는 순서가 다르기만 하면 서로 다른 해밀턴 경로다.

IO Example

입력
3 1000000

출력
12


입력
2 1000

출력
4

입력
3 1

출력
0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]