I have AC at 0.14 sec, but I can see there are lot of faster solutions.
So how did you optimize your solution so hard ??

hi, maybe the answer with powers from 2 to N+1 is always identical to given at this task(my AC is less than 0.14), also use some breaks like if (a[i][j] is already 1 then halt from cell computation etc.)

send at night ))