시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 83 62 47 85.455%

문제

2 타워의 높이 H는\[2^{2^{2^{\cdot^{\cdot^{\cdot 2}}}}}\]에서 숫자 2가 나타나는 횟수로 정의된다. 2 타워의 값은 해당 표현식의 값으로 정의된다. 예를 들어, 높이 1의 2 타워 값은 2이고, 높이 2의 2 타워 값은 4이며, 높이 4의 2 타워 값은\[2^{2^{2^{2}}} = 65536\]이므로 높이 5의 2 타워 값은 265536이며 이 값은 2003...6736이고 다 쓰기에는 여백이 부족하다.

H의 값이 커짐에 따라 2 타워의 값이 너무 커지므로, 우리는 이 값을 3으로 나눈 나머지만이 궁금하다.

입력

입력의 첫째 줄에 높이 H가 주어진다. (1 ≤ H ≤ 10100)

출력

첫째 줄에 높이가 H인 2 타워의 값을 3으로 나눈 나머지를 출력하라.

예제 입력 1

1

예제 출력 1

2

예제 입력 2

2

예제 출력 2

1

예제 입력 3

99999999999999999999

예제 출력 3

1
W3sicHJvYmxlbV9pZCI6IjEwNDA3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiMiBcdWQwYzBcdWM2Y2MiLCJkZXNjcmlwdGlvbiI6IjxwPjIgXHVkMGMwXHVjNmNjXHVjNzU4IFx1YjE5Mlx1Yzc3NCBIXHViMjk0XFxbMl57Ml57Ml57XFxjZG90XntcXGNkb3Ree1xcY2RvdCAyfX19fX1cXF1cdWM1ZDBcdWMxMWMgXHVjMjJiXHVjNzkwIDJcdWFjMDAgXHViMDk4XHVkMGMwXHViMDk4XHViMjk0IFx1ZDY5Zlx1YzIxOFx1Yjg1YyBcdWM4MTVcdWM3NThcdWI0MWNcdWIyZTQuIDIgXHVkMGMwXHVjNmNjXHVjNzU4IFx1YWMxMlx1Yzc0MCBcdWQ1NzRcdWIyZjkgXHVkNDVjXHVkNjA0XHVjMmRkXHVjNzU4IFx1YWMxMlx1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NThcdWI0MWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YjE5Mlx1Yzc3NCAxXHVjNzU4IDIgXHVkMGMwXHVjNmNjIFx1YWMxMlx1Yzc0MCZuYnNwOzJcdWM3NzRcdWFjZTAsIFx1YjE5Mlx1Yzc3NCAyXHVjNzU4IDIgXHVkMGMwXHVjNmNjIFx1YWMxMlx1Yzc0MCZuYnNwOzRcdWM3NzRcdWJhNzAsIFx1YjE5Mlx1Yzc3NCA0XHVjNzU4IDIgXHVkMGMwXHVjNmNjIFx1YWMxMlx1Yzc0MFxcWzJeezJeezJeezJ9fX0gPSA2NTUzNlxcXVx1Yzc3NFx1YmJjMFx1Yjg1YyBcdWIxOTJcdWM3NzQgNVx1Yzc1OCAyIFx1ZDBjMFx1YzZjYyBcdWFjMTJcdWM3NDAgMjxzdXA+NjU1MzY8XC9zdXA+XHVjNzc0XHViYTcwIFx1Yzc3NCBcdWFjMTJcdWM3NDAgMjAwMy4uLjY3MzZcdWM3NzRcdWFjZTAmbmJzcDtcdWIyZTQgXHVjNGYwXHVhZTMwXHVjNWQwXHViMjk0IFx1YzVlY1x1YmMzMVx1Yzc3NCBcdWJkODBcdWM4NzFcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkhcdWM3NTggXHVhYzEyXHVjNzc0IFx1Y2VlNFx1YzlkMFx1YzVkMCBcdWI1MzBcdWI3N2MgMiBcdWQwYzBcdWM2Y2NcdWM3NTggXHVhYzEyXHVjNzc0IFx1YjEwOFx1YmIzNCBcdWNlZTRcdWM5YzBcdWJiYzBcdWI4NWMsIFx1YzZiMFx1YjlhY1x1YjI5NCBcdWM3NzQgXHVhYzEyXHVjNzQ0IDNcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1YjljY1x1Yzc3NCBcdWFkODFcdWFlMDhcdWQ1NThcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiXHVjOWY4Jm5ic3A7XHVjOTA0XHVjNWQwJm5ic3A7XHViMTkyXHVjNzc0IEhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEggJmxlOyAxMDxzdXA+MTAwPFwvc3VwPik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjE5Mlx1Yzc3NFx1YWMwMCBIXHVjNzc4IDIgXHVkMGMwXHVjNmNjXHVjNzU4IFx1YWMxMlx1Yzc0NCAzXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwNDA3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIHR3byB0b3dlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgdHdvIHRvd2VyIG9mIGhlaWdodCBIIGlzIGEgbWF0aGVtYXRpY2FsIGV4cHJlc3Npb24gb2YgdGhlIGZvcm08XC9wPlxyXG5cclxuPHA+XFxbXFxkZWZcXGlkZG90c3t7XFxrZXJuM211XFxyYWlzZTFtdXsufVxca2VybjNtdVxccmFpc2U2bXV7Ln1cXGtlcm4zbXUgJm5ic3A7XFxyYWlzZTEybXV7Ln19fSZuYnNwOzJeezJeezJee1xcaWRkb3RzXnsyfX19fVxcXTxcL3A+XHJcblxyXG48cD53aXRoIHRoZSBudW1iZXIgdHdvIGFwcGVhcmluZyBleGFjdGx5IEggdGltZXMuIFRoZSB2YWx1ZSBvZiBhIHR3byB0b3dlciBpcyB0aGUgdmFsdWUgb2YgdGhlIGNvcnJlc3BvbmRpbmcgZXhwcmVzc2lvbi4gRm9yIGluc3RhbmNlLCB0aGUgdmFsdWUgb2YgdGhlIHR3byB0b3dlciBvZiBoZWlnaHQgMSBpcyAyLCB0aGUgdmFsdWUgb2YgdGhlIHR3byB0b3dlciBvZiBoZWlnaHQgMiBpcyAyPHN1cD4yPFwvc3VwPiA9IDQgYW5kIHRoZSB2YWx1ZSBvZiB0aGUgdHdvIHRvd2VyIG9mIGhlaWdodCA0IGlzPFwvcD5cclxuXHJcbjxwPlxcWyAyXnsyXnsyXjJ9fSA9IDY1NTM2XFxdPFwvcD5cclxuXHJcbjxwPlRoZSB2YWx1ZSBvZiB0aGUgdHdvIHRvd2VyIG9mIGhlaWdodCA1IGlzIHRoZXJlZm9yZSAyPHN1cD42NTUzNjxcL3N1cD4gYW5kIHRoZXJlIGlzIG5vdCBlbm91Z2ggc3BhY2Ugb24gdGhpcyBzaGVldCBvZiBwYXBlciB0byB3cml0ZSBpdCBpbiBmdWxsLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGF0IHRoZSB2YWx1ZXMgb2YgdHdvIHRvd2VycyBjYW4gZ3JvdyByZWFsbHkgYmlnLCB3ZSBhcmUgd29uZGVyaW5nIGlmIHlvdSBjYW4gaGVscCB1cyBmaW5kIHRoZSByZW1haW5kZXIgb2Ygc3VjaCB2YWx1ZXMgd2hlbiBkaXZpZGVkIGJ5IDMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSB0aGF0IGNvbnRhaW5zIGFuIGludGVnZXIgSCByZXByZXNlbnRpbmcgdGhlIGhlaWdodCBvZiB0aGUgdHdvIHRvd2VyIHdlIHdhbnQgdG8gY29uc2lkZXIgKDEgJmxlOyBIICZsZTsgMTA8c3VwPjEwMDxcL3N1cD4pLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBhIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIHJlcHJlc2VudGluZyB0aGUgcmVtYWluZGVyIG9mIGRpdmlkaW5nIHRoZSB2YWx1ZSBvZiB0aGUgdHdvIHRvd2VyIG9mIGhlaWdodCBIIGJ5IDMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d