#include<stdio.h>
long long int a[1000005];
int n;
int dp(int n) {
if (n == 1)return 0;
if (n == 2)return 1;
if (a[n] != 0) return a[n];
return a[n] = (n-1)*(dp(n-1)+dp(n-2)) % 1000000000;
}
int main() {
}
I2luY2x1ZGU8c3RkaW8uaD4KCgoKbG9uZyBsb25nIGludCBhWzEwMDAwMDVdOwppbnQgbjsKCmludCBkcChpbnQgbikgewoJaWYgKG4gPT0gMSlyZXR1cm4gMDsKCWlmIChuID09IDIpcmV0dXJuIDE7CglpZiAoYVtuXSAhPSAwKSByZXR1cm4gYVtuXTsKCXJldHVybiBhW25dID0gKG4tMSkqKGRwKG4tMSkrZHAobi0yKSkgJSAxMDAwMDAwMDAwOwp9CgppbnQgbWFpbigpIHsKCXNjYW5mKCIlZCIsICZuKTsKCXByaW50ZigiJWQiLCBkcChuKSk7CgoJCgoKCn0=