import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
 
public class Main {
 
public static void main (String args []) throws Exception{
	BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
 
	int m = Integer.parseInt(reader.readLine());
 
	for(String line = reader.readLine(); line != null; line = reader.readLine()){
		int n = Integer.parseInt(line);
		int fibn = (int) ((int)((1/Math.sqrt(5))* (Math.pow((1 + Math.sqrt(5))/2, n) - Math.pow((1 - Math.sqrt(5))/2, n)))% m);
		System.out.println(fibn); 
		}
 
}
}
 
 
 

aW1wb3J0IGphdmEuaW8uQnVmZmVyZWRSZWFkZXI7CmltcG9ydCBqYXZhLmlvLklPRXhjZXB0aW9uOwppbXBvcnQgamF2YS5pby5JbnB1dFN0cmVhbVJlYWRlcjsKCgpwdWJsaWMgY2xhc3MgTWFpbiB7CgkKcHVibGljIHN0YXRpYyB2b2lkIG1haW4gKFN0cmluZyBhcmdzIFtdKSB0aHJvd3MgRXhjZXB0aW9uewoJQnVmZmVyZWRSZWFkZXIgcmVhZGVyID0gbmV3IEJ1ZmZlcmVkUmVhZGVyKG5ldyBJbnB1dFN0cmVhbVJlYWRlcihTeXN0ZW0uaW4pKTsKCQoJaW50IG0gPSBJbnRlZ2VyLnBhcnNlSW50KHJlYWRlci5yZWFkTGluZSgpKTsKCQoJZm9yKFN0cmluZyBsaW5lID0gcmVhZGVyLnJlYWRMaW5lKCk7IGxpbmUgIT0gbnVsbDsgbGluZSA9IHJlYWRlci5yZWFkTGluZSgpKXsKCQlpbnQgbiA9IEludGVnZXIucGFyc2VJbnQobGluZSk7CgkJaW50IGZpYm4gPSAoaW50KSAoKGludCkoKDEvTWF0aC5zcXJ0KDUpKSogKE1hdGgucG93KCgxICsgTWF0aC5zcXJ0KDUpKS8yLCBuKSAtIE1hdGgucG93KCgxIC0gTWF0aC5zcXJ0KDUpKS8yLCBuKSkpJSBtKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oZmlibik7IAoJCX0KCQp9Cn0KCgo=

MTAwMAo5OTk5NQo5OTk5Ngo5OTk5Nwo5OTk5OAo5OTk5OQoxMDAwMDAKMTAwMDAwMDA=

1000
99995
99996
99997
99998
99999
100000
10000000