fork(24) download
  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.  
  5. private Scanner scanner;
  6. private int mod;
  7.  
  8. private Main(Scanner scanner) {
  9. this.scanner = scanner;
  10. }
  11.  
  12. public static void main(String[] args) {
  13. Main main = new Main(new Scanner(System.in));
  14. main.solve();
  15. }
  16.  
  17. private void solve() {
  18. long n = scanner.nextLong();
  19. long k = scanner.nextLong();
  20. int l = scanner.nextInt();
  21. mod = scanner.nextInt();
  22. if (mod == 1 || l < 63 && 1l << l <= k) {
  23. System.out.println(0);
  24. return;
  25. }
  26. if (l == 0) {
  27. if (k == 0) System.out.println(1);
  28. else
  29. System.out.println(0);
  30. return;
  31. }
  32. long pow2 = fastPower(2, n);
  33. long fib = fibonacci(n + 1);
  34. long res = 1;
  35. for (int i = 0; i < l; i++)
  36. if (((k >> i) & 1) == 0) res = res * fib % mod;
  37. else
  38. res = res * (pow2 - fib) % mod;
  39. if (res < 0) res += mod;
  40. System.out.println(res);
  41. }
  42.  
  43. private long fibonacci(long n) {
  44. Matrix matrix = new Matrix(new long[][]{{1, 1}, {1, 0}});
  45. matrix = fastPower(matrix, n);
  46. return matrix.matrix[0][0];
  47. }
  48.  
  49. private long fastPower(long base, long exponent) {
  50. if (exponent == 0) return 1;
  51. long x = fastPower(base, exponent >> 1);
  52. x = x * x % mod;
  53. if ((exponent & 1) != 0) x = x * base % mod;
  54. return x;
  55. }
  56.  
  57. private Matrix fastPower(Matrix base, long exponent) {
  58. if (exponent == 1) return base;
  59. Matrix x = fastPower(base, exponent >> 1);
  60. x = multiplyMatrix(x, x);
  61. if ((exponent & 1) != 0) x = multiplyMatrix(x, base);
  62. return x;
  63. }
  64.  
  65. private Matrix multiplyMatrix(Matrix a, Matrix b) {
  66. Matrix matrix = new Matrix();
  67. for (int i = 0; i < 2; i++)
  68. for (int j = 0; j < 2; j++)
  69. for (int k = 0; k < 2; k++)
  70. matrix.matrix[i][k] = (matrix.matrix[i][k] + a.matrix[i][j] * b.matrix[j][k]) % mod;
  71. return matrix;
  72. }
  73.  
  74. private class Matrix {
  75.  
  76. private long[][] matrix;
  77.  
  78. public Matrix() {
  79. matrix = new long[2][2];
  80. }
  81.  
  82. public Matrix(long[][] c) {
  83. matrix = c.clone();
  84. }
  85. }
  86. }
Runtime error #stdin #stdout #stderr 0.15s 321088KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
Exception in thread "main" java.util.NoSuchElementException
	at java.util.Scanner.throwFor(Scanner.java:862)
	at java.util.Scanner.next(Scanner.java:1485)
	at java.util.Scanner.nextLong(Scanner.java:2222)
	at java.util.Scanner.nextLong(Scanner.java:2182)
	at Main.solve(Main.java:18)
	at Main.main(Main.java:14)