시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB158853.333%

문제

Bajtazar wymyśla ciąg liczb naturalnych: rozpoczyna od swojej ulubionej liczby X (czyli pierwszy wyraz ciągu A1 = X), natomiast każda kolejna liczba w ciągu to dwukrotność sumy cyfr poprzedniej (czyli dla każdego i ≥ 1 zachodzi Ai+1 = 2 · s(Ai), gdzie s(k) oznacza sumę cyfr k). Na przykład, jeśli X = 1, to pierwszymi wyrazami tego będą A1 = 1, A2 = 2, A3 = 4, A4 = 8, A5 = 16, A6 = 14, . . . .

Czy potrafisz szybko wyznaczyć N-ty wyraz ciągu? Napisz program, który wczyta wartości N oraz X, po czym wyznaczy N-ty wyraz ciągu Bajtazara rozpoczynającego się od X.

입력

W pierwszym (jedynym) wierszu wejścia znajdują się dwie liczby naturalne N oraz X (1 ≤ N, X ≤ 1018).

출력

Twój program powinien wypisać na wyjście jedną liczbę całkowitą: N-ty wyraz ciągu Bajtazara, czyli element AN.

예제 입력 1

6 1

예제 출력 1

14

Wyjaśnienie do przykładu: Jest to ciąg z treści zadania, jako że X = 1. Pytamy się o szósty element, zatem odpowiedzią jest A6 = 14.

예제 입력 2

4 9912

예제 출력 2

6

Wyjaśnienie do przykładu: Kolejne elementy ciągu to A1 = 9912, A2 = 2·(9+9+1+2) = 2·21 = 42, A3 = 2·(4+2) = 2·6 = 12, A4 = 2 · (1 + 2) = 2 · 3 = 6, zatem odpowiedzią jest 6.