Однажды одна маленькая девочка попала в плен к большому людоеду. Понятное дело, что перед тем, как съесть её, людоед решил хорошенько выспаться.

Людоед и девочка, к слову сказать, жили в волшебном Царстве. А Царство это было волшебным потому, что в 13231 году до нашей эры Баба Яга решила, что оно будет волшебным. Волшебство этого Царства, как выяснилось после применения новейших технологий, заключается в том, что все слова, одинаково читающиеся как справа налево, так и слева направо, называются милыми и обладают огромной магической силой. Сила таких слов равна максимальному натуральному числу, для которого верно, что некоторые два числа \(1\le N,M\le10^{189}\), делятся оба на него. Только не ему самому, а возведенному в степень, равной сумме кодов символов, входящих в слово.

Числа \(N\) и \(M\) напрямую зависят от того, как сложились звезды в тот день, когда Баба Яга создавала этот замечательный, чудесный, великолепный волшебный мир. А звезды, как известно, не могут складываться как попало: они могут складываться только в два непересекающихся многоугольника, в первом из них \(1\le P\le10^{189}\) вершин, во втором - \(1\le Q\le10^{189}\) вершин. К сожалению, до сих пор ученые не выяснили, как именно \(N\) и \(M\) зависят от \(P\) и \(Q\), однако наиболее вероятным является тот факт, что \(N=A_P\), а \(M=A_Q\), где \(A_i\) - \(i\) по счету простое число Мерсенна.

Девочка конечно же знала о магической силе этого мира. Но она понимала, что и людоед, который прожил на этом свете гораздо больше неё, может применить эту силу против неё. Однако, людоеды не отличаются высоким IQ. Поэтому произносимое людоедами заклинание всем давно известно. Это строка, состоящая из маленьких латинских букв, длина которой не превосходит 250.

Однако этот людоед отличался от остальных. В детстве он случайно попал на полянку к ученым. Тогда у него еще не отросли зубы, и он не стал есть их. За это они поведали ему тайной знание. Тайное знание заключалось в том, что силой обладают не только сами милые строки, но и их конкатенация (т.е. склейка). Причем сила таких липких и клейких строк равна сумме сил их составляющих милых строк. С этим тайным знанием он отправился домой и рассказал это знакомой обезьянке. Она сразу же догадалась, что липкую строку можно не единственным способом разбить на милые. И она, рассмотрев простой пример, поняла, что сила строки зависит от разбиения! Она, разумеется, рассказала это людоеду. В ответ он, угрожая ей смертью через переваривание, потребовал у неё самое сильное разбиение... Но обезьянка знала об уровне развития людоедов. И вместо того, чтобы дать ему максимально сильное разбиение, она дала ему самое слабое разбиение. С тех пор прошло много времени, но людоеды по-прежнему используют самое слабое разбиение.
Девочка чудесным образом от своей прабабушки узнала эту замечательную историю. И она хочет вычислить, какой же силой обладает заклинание, которое применит против нее людоед. Однако у нее мало времени, ведь скоро людоед проснется, поэтому она обратилась за помощью к Вам.

Формат входных данных

В первой строке входного файла содержится заклинание людоедов. Во второй строке содержится число \(P\), в третьей - число \(Q\).

Формат выходных данных

Выведите одно число - ответ на задачу

Пример