fork(24) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
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)
https://ideone.com/bdDxMn
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!