## Editorial for DMPG '17 S3 - Black and White III

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

Let us consider first the case where there is only black square. Unfolding a move produces possible locations for the original square(s). Thus the number of possible original black squares after undoing moves is . The number of ways to select a non-empty subset of these squares is . Let be the number of black squares in the original grid. Thus our final formula is .

To compute , we can apply Fermat's Little Theorem, to get .

Time Complexity: , where , by using exponentiation by squaring to quickly compute the exponents.

Why is the mod instead of for ?
Notice FLT shows us that for prime where is coprime to . In this problem we have and . Since we wish to find , notice for some , and since we know , we know , so it boils down to finding the such that , where , and this is where you'd use your normal mod operator to find the remainder .