Мытищинский тракторный завод собирается наладить выпуск своих калькуляторов. Бизнес-план заключается в том, чтобы выпустить на рынок много дешёвых моделей, которые способны выполнять только одну операцию. Например, уже оборудован цех, который выпускает калькуляторы, которые складывают два числа, и цех, который выпускает калькуляторы, способные вычитать из одного числа другое.

Главный инжеренер завода также решил позаботиться и об эстетах арифметического дела и начал проектировать калькулятор, который может возвести число a в степень b. Поскольку калькулятор все-таки ограничен в вычислительных мощностях, он выводит только последние шесть цифр результата.

Требуется написать программу, которая поможет инженеру протестировать эту модель, а именно вычислит последние шесть цифр числа a^b.

Даны натуральные числа \(a\), \(b\), \(c\). Если уравнение \(ax+by=c\) имеет решения в целых числах, то выберите то решение, в котором число \(x\) имеет наименьшее неотрицательное значение и выведите это решение (два числа \(x\) и \(y\) через один пробел). Если решения не существует, то выведите слово Impossible.

Дано натуральное число \(n \le 10^8\). Подсчитайте количество таких пар чисел \((a, b)\), что:

1. \(a\) и \(b\) — делители \(n\).
2. \(a < b\).
3. \(a\) и \(b\) — взаимно простые.
4. \(ab\le n\).

Митя знаком с \(m\) юношами и \(n\) девушками и хочет пригласить часть из них на свой день рождения. Ему известно, с какими девушками знаком каждый юноша, и с какими юношами знакома каждая девушка. Он хочет добиться того, чтобы каждый приглашённый был знаком со всеми приглашёнными противоположного пола, пригласив при этом максимально возможное число своих знакомых.

На планете Руук существует Большая Корпорация Маленьких Фей. Одним из видов деятельности, которым испокон веков занимаются ее сотрудницы, является посадка грядок с волшебными грибами. Каждый день, начиная с самого первого дня существования этой корпорации, феи создают одну новую грядку грибов. После этого с новой грядки два дня можно собирать споры, которыми размножаются эти грибы, а потом грядка будет поставлять уже только сам продукт — грибы.

Таким образом, если обозначить количество грибов, посаженных на грядке, созданной в день номер i, как c_i, то оно будет считаться по формуле c_i = c_i - 1 + c_i - 2. Так, в первый и второй дни было посажено по одному грибу, в третий — два, в четвертый — три, в пятый — пять и так далее.

Волшебные грибы являются самыми ценными сувенирами, которые путешественник может привезти с планеты Руук. Поэтому первым, что делает любой приезжий, становится поиск грядки с волшебными грибами. Однако, в последнее время все чаще стали появляться сообщения о поддельных волшебных грибах. Тщательное расследование показало, что это является следствием действий Маленькой Корпорации Больших Фей, которая сажает грядки с грибами, внешне не отличимыми, но далеко не такими ценными, как волшебные. Причем, создавая очередную грядку, эти феи сажают туда такое количество грибов, какое их соперницы никогда не сажали и не смогут посадить.

Казалось бы, после выяснения этого факта отличать волшебные грядки от поддельных стало просто. Но обе корпорации существуют достаточно давно, количество грядок и грибов на них давно превысило все разумные пределы. Вас попросили написать программу, по количеству грибов на грядке сообщающую, является ли эта грядка волшебной.