object Main extends App{
    for(i <- 1 to 50)
      println(task(i, 10000))
  def task(n: Long, m: Int): Int = (new State(Array(Array(1, 1),Array(1, 0)),m) ^^ n).mm(1)(0)
}
  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)
    }
  }
 
 

b2JqZWN0IE1haW4gZXh0ZW5kcyBBcHB7CiAgICBmb3IoaSA8LSAxIHRvIDUwKQogICAgICBwcmludGxuKHRhc2soaSwgMTAwMDApKQogIGRlZiB0YXNrKG46IExvbmcsIG06IEludCk6IEludCA9IChuZXcgU3RhdGUoQXJyYXkoQXJyYXkoMSwgMSksQXJyYXkoMSwgMCkpLG0pIF5eIG4pLm1tKDEpKDApCn0KICBjbGFzcyBTdGF0ZSh2YWwgbW06QXJyYXlbQXJyYXlbSW50XV0sIHZhbCBtOkludCkgewogICAgZGVmIF5eKG4gOiBMb25nKTogU3RhdGUgPSBuIG1hdGNoIHsKICAgICAgY2FzZSAxID0+IHRoaXMKICAgICAgY2FzZSBfIGlmIG4gJSAyID09IDAgPT4gdmFsIHAgPSB0aGlzIF5eIChuIC8gMik7IHAgKiogcAogICAgICBjYXNlIF8gaWYgbiAlIDIgPT0gMSA9PiB2YWwgcCA9IHRoaXMgXl4gKG4gLyAyKTsgcCAqKiBwICoqIHRoaXMKICAgICAgY2FzZSBfID0+ID8/PwogICAgfQoKICAgIGRlZiAqKih5OiBTdGF0ZSk6IFN0YXRlID0gewogICAgICBuZXcgU3RhdGUoCiAgICAgICAgZm9yKHJvdyA8LSBtbSkKICAgICAgICAgIHlpZWxkIGZvcihjb2wgPC0geS5tbS50cmFuc3Bvc2UpCiAgICAgICAgICAgIHlpZWxkIChyb3cgemlwIGNvbCBtYXAgRnVuY3Rpb24udHVwbGVkKF8gKiBfKSkuc3VtICUgbSwgbSkKICAgIH0KICB9Cgo=