scala
scala\nobject Solution {\n  def findProductsOfElements(queries: Array[Array[Long]]): Array[Int] = {\n    def calc(p: Int, lim: Long): Long = {\n      val len = 
```scala\nobject Solution {\n  def findProductsOfElements(queries: Array[Array[Long]]): Array[Int] = {\n    def calc(p: Int, lim: Long): Long = {\n      val len = 1L << p\n      val len2 = len * 2\n      val ret = lim / len2 * len + (if (lim % len2 >= len) lim % len2 - len + 1 else 0)\n      ret\n    }\n\n    def countOne(x: Long): Long = {\n      def g(x: Long, p: Int): Long =\n        if ((1L << p) > x) 0L\n        else calc(p, x) + g(x, p + 1)\n\n      g(x, 0)\n    }\n\n    def findPos(x: Long): (Long, Int) = {\n      @scala.annotation.tailrec\n      def binarySearch(head: Long, tail: Long): (Long, Int) =\n        if (head >= tail) (head, (x - countOne(head - 1)).toInt)\n        else {\n          val mid = (head + tail) >> 1\n          if (countOne(mid) >= x) binarySearch(head, mid)\n          else binarySearch(mid + 1, tail)\n        }\n\n      binarySearch(1L, x)\n    }\n\n    def gao1(x: Long, L: Int, R: Int, M: Int): Long = {\n      var ret = 1L\n      var p = 0\n      var i = 0\n      while ((1L << p) <= x) {\n        if ((x >> p & 1) == 1) {\n          i += 1\n          if (L <= i && i <= R) ret = (1L << p) % M * ret % M\n        }\n        p += 1\n      }\n      ret\n    }\n\n    def power(a: Long, b: Long, M: Int): Long = {\n      @scala.annotation.tailrec\n      def g(aa: Long, bb: Long, y: Long): Long =\n        if (bb == 0) y\n        else {\n          val new_y = if ((bb & 1) == 1) y * aa % M else y\n          val new_aa = aa * aa % M\n          val new_bb = bb >> 1\n          g(new_aa, new_bb, new_y)\n        }\n\n      g(a, b, 1L)\n    }\n\n\n    def gao2(L: Long, R: Long, M: Int): Long = {\n      @scala.annotation.tailrec\n      def g(p: Int, ret: Long): Long =\n        if ((1L << p) > R) ret\n        else {\n          val cnt = calc(p, R) - calc(p, L - 1)\n          val newRet = ret * power((1L << p) % M, cnt, M) % M\n          g(p + 1, newRet)\n        }\n\n      g(0, 1L)\n    }\n\n    queries.map(qry => {\n      val L = findPos(qry.head + 1)\n      val R = findPos(qry(1) + 1)\n      if (L._1 == R._1) gao1(L._1, L._2, R._2, qry(2).toInt).toInt\n      else {\n        val t = gao1(L._1, L._2, 1000000000, qry(2).toInt) * gao1(R._1, 1, R._2, qry(2).toInt) % qry(2)\n        (t * gao2(L._1 + 1, R._1 - 1, qry(2).toInt) % qry(2)).toInt\n      }\n    })\n  }\n}\n```
['Scala']