문제

아스트로파지(Astrophage)는 항성의 빛을 흡수하여 번식하는 외계 미생물이다.

아스트로파지로 인해 태양 빛이 감소하기 시작했고, 준호는 국가의 명령을 받아 아스트로파지를 연구했다.

준호의 연구 결과, 아스트로파지는 다음과 같은 성질을 갖고 있다.

• 에너지가 인 아스트로파지 한 마리는 하루 뒤, 에너지가 , 인 아스트로파지 두 마리로 분열한다.
• 이때, 이라면 에너지가 인 아스트로파지는 생성되지 않는다.

준호는 현재 에너지가 인 아스트로파지 한 마리가 일 뒤 몇 마리로 늘어날지 예측하려 한다. 준호를 도와 문제의 정답을 구해 보자.

입력

첫째 줄에 과 가 공백으로 구분되어 주어진다.

출력

문제의 정답을 로 나눈 나머지를 출력한다.

제약 조건

• 입력으로 주어지는 모든 수는 정수이다.