def main(args: Array[String]) = {
    for(i <- 1 to 20)
      println(task(Math.pow(10,i).toLong, 12354))
  }

  class State(val mm:Array[Array[Int]], val m:Int) {
    def ^^(n : Long): State = n match {
      case 1 => this
      case _ if n % 2 == 0 => val p = this ^^ (n / 2); p ** p
      case _ if n % 2 == 1 => val p = this ^^ (n / 2); p ** p ** this
      case _ => ???
    }

    def **(y: State): State = {
      new State(
        for(row <- mm)
          yield for(col <- y.mm.transpose)
            yield (row zip col map Function.tupled(_ * _)).sum % m, m)
    }
  }
  def task(n: Long, m: Int): Int = (new State(Array(Array(1, 1),Array(1, 0)),m) ^^ n).mm(1)(0)