#include<stdio.h>
#define m 1000000007
long long int fact(long long int n){
if(n == 1)
return (1);
long long int n2 = (long long int)(fact(n-1));
long long int k = (n*n2)%m;
return k;
}
int main(){
}
I2luY2x1ZGU8c3RkaW8uaD4KI2RlZmluZSBtIDEwMDAwMDAwMDcKCmxvbmcgbG9uZyBpbnQgZmFjdChsb25nIGxvbmcgaW50IG4pewppZihuID09IDEpCiAgICByZXR1cm4gKDEpOwpsb25nIGxvbmcgaW50IG4yID0gKGxvbmcgbG9uZyBpbnQpKGZhY3Qobi0xKSk7CmxvbmcgbG9uZyBpbnQgayA9IChuKm4yKSVtOwpyZXR1cm4gazsKfQoKaW50IG1haW4oKXsKcHJpbnRmKCIlbGxkIixmYWN0KDEwMDAwMDApKTsKfQo=