// 2023.04.15 at 22:20:44 HKT import java.io.BufferedInputStream import java.io.File import java.io.PrintWriter import kotlin.system.measureTimeMillis import java.util.TreeMap import java.util.TreeSet import kotlin.random.Random import kotlin.random.nextInt // 1. Modded const val p = 1000000007L const val pI = p.toInt() fun Int.adjust():Int{ if(this >= pI){ return this - pI }else if (this < 0){ return this + pI };return this } fun Int.snap():Int{ if(this >= pI){return this - pI} else return this} infix fun Int.mm(b:Int):Int{ return ((this.toLong() * b) % pI).toInt() } infix fun Int.mp(b:Int):Int{ val ans = this + b;return if(ans >= pI) ans - pI else ans } infix fun Int.ms(b:Int):Int{ val ans = this - b;return if(ans < 0) ans + pI else ans } fun Int.inverse():Int = intPow(this,pI-2,pI) infix fun Int.modDivide(b:Int):Int{ return this mm (b.inverse()) } fun intPow(x:Int,e:Int,m:Int):Int{ var X = x ; var E =e ; var Y = 1 while(E > 0){ if(E and 1 == 0){ X = ((1L * X * X) % m).toInt() E = E shr 1 }else{ Y = ((1L * X * Y) % m).toInt() E -= 1 } } return Y } // 2. DP initial values const val plarge = 1_000_000_727 const val nlarge = -plarge const val phuge = 2_727_000_000_000_000_000L const val nhuge = -phuge // 3. convenience conversions val Boolean.chi:Int get() = if(this) 1 else 0 //characteristic function val BooleanArray.chiarray:IntArray get() = IntArray(this.size){this[it].chi} val Char.code :Int get() = this.toInt() - 'a'.toInt() //3. hard to write stuff fun IntArray.put(i:Int,v:Int){ this[i] = (this[i] + v).adjust() } val mint:MutableList get() = mutableListOf() val mong:MutableList get() = mutableListOf() val mchar:MutableList get() = mutableListOf() //4. more outputs fun List.conca():String = this.joinToString("") val CharArray.conca :String get() = this.joinToString("") val IntArray.conca :String get() = this.joinToString(" ") @JvmName("concaInt") fun List.conca():String = this.joinToString(" ") val LongArray.conca:String get() = this.joinToString(" ") @JvmName("concaLong") fun List.conca():String = this.joinToString(" ") //5. Pair of ints const val longmask = (1L shl 32) - 1 fun makepair(a:Int, b:Int):Long = (a.toLong() shl 32) xor (longmask and b.toLong()) val Long.first get() = (this ushr 32).toInt() val Long.second get() = this.toInt() //6. strings val String.size get() = this.length const val randCount = 100 //7. bits fun Int.has(i:Int):Boolean = (this and (1 shl i) != 0) fun Long.has(i:Int):Boolean = (this and (1L shl i) != 0L) //8 TIME inline fun TIME(f:()->Unit){ val t = measureTimeMillis(){ f() } println("$t ms") } //9.ordered pair fun order(a:Int, b:Int):Pair{ return Pair(minOf(a,b), maxOf(a,b)) } //10 rand fun rand(x:Int) = Random.nextInt(x) fun rand(x:IntRange) = Random.nextInt(x) val coin:Boolean get() = Random.nextBoolean() //11 typing issues, rename typealias ints = IntArray typealias longs = LongArray typealias bools = BooleanArray typealias pii = Pair const val interactive = false object Reader{ private const val BS = 1 shl 16 private const val NC = 0.toChar() private val buf = ByteArray(BS) private var bId = 0 private var size = 0 private var c = NC var warningActive = true var fakein = StringBuilder() private var IN: BufferedInputStream = BufferedInputStream(System.`in`, BS) val OUT: PrintWriter = PrintWriter(System.out) private val char: Char get() { if(interactive){ return System.`in`.read().toChar() } while (bId == size) { size = IN.read(buf) // no need for checked exceptions if (size == -1) return NC bId = 0 } return buf[bId++].toChar() } fun nextInt(): Int { var neg = false if (c == NC) c = char while (c < '0' || c > '9') { if (c == '-') neg = true c = char } var res = 0 while (c in '0'..'9') { res = (res shl 3) + (res shl 1) + (c - '0') c = char } return if (neg) -res else res } fun nextLong(): Long { var neg = false if (c == NC) c = char while (c < '0' || c > '9') { if (c == '-') neg = true c = char } var res = 0L while (c in '0'..'9') { res = (res shl 3) + (res shl 1) + (c - '0') c = char } return if (neg) -res else res } fun nextString():String{ val ret = StringBuilder() while (true){ c = char if(!isWhitespace(c)){ break} } ret.append(c) while (true){ c = char if(isWhitespace(c)){ break} ret.append(c) } return ret.toString() } fun isWhitespace(c:Char):Boolean{ return c == ' ' || c == '\n' || c == '\r' || c == '\t' } fun rerouteInput(){ if(warningActive){ put("Custom test enabled") println("Custom test enabled") warningActive = false } val S = fakein.toString() println("New Case ") println(S.take(80)) println("...") fakein.clear() IN = BufferedInputStream(S.byteInputStream(),BS) } fun flush(){ OUT.flush() } fun takeFile(name:String){ IN = BufferedInputStream(File(name).inputStream(),BS) } } fun eat(){ val st1 = TreeSet(); val st2 = TreeMap()} fun put(aa:Any){ Reader.OUT.println(aa) if(interactive){ Reader.flush()} } fun put(vararg x:Any){ for(c in x){ Reader.OUT.print(c) Reader.OUT.print(" ") } Reader.OUT.print("\n") if(interactive){ Reader.flush()} } fun done(){ Reader.OUT.close() } fun share(aa:Any){ Reader.fakein.append(format(aa)) Reader.fakein.append("\n") } val getintfast:Int get() = Reader.nextInt() val getint:Int get(){ val ans = getlong ; if(ans > Int.MAX_VALUE) IntArray(1000000000); return ans.toInt() } val getlong:Long get() = Reader.nextLong() val getstr:String get() = Reader.nextString() fun getline(n:Int):IntArray{ return IntArray(n){getint} } fun getlineL(n:Int):LongArray{ return LongArray(n){getlong} } fun subformat(a:Any?):String{ // for not a collection return if(a == null) "null" else if(a is Iterable<*> ) a.joinToString(" ") else if(a is BooleanArray) a.joinToString("") { if (it) "1" else "0" } else if(a is IntArray) a.joinToString(" ") else if(a is LongArray) a.joinToString(" ") else a.toString() } fun format(a:Any?):String { if (a == null) { return "null" } else if (a is BooleanArray) { return a.joinToString("") { if (it) "1" else "0" } } else if (a is Array<*>) { return "\n"+a.joinToString("\n"){subformat(it)} } else { return subformat(a)} } var dmark = -1 infix fun Any.dei(a:Any?){ dmark++ ; debug() println("<${dmark}> ${this} : ${format(a)}") } const val just = " " fun crash(){ throw Exception("Bad programme")} fun assert(a:Boolean){ if(!a){ throw Exception("Failed Assertion") }} enum class solveMode { real, rand, tc } object solve{ var mode:solveMode = solveMode.real var tcNum:Int = 0 var rand:()->Unit = {} var TC:MutableMapUnit> = mutableMapOf() var tn:Long = 0 fun cases(onecase:()->Unit){ val t = if(mode == solveMode.real){if(singleCase) 1 else getint} else if(mode == solveMode.tc){1 } else randCount if(pI != 998_244_353 && pI != 1_000_000_007){ throw Exception("Not usual primes!") } if(t == 1 && mode != solveMode.real){ tn = System.currentTimeMillis() } repeat(t){ if(mode == solveMode.tc){ TC[tcNum]?.let { it() } Reader.rerouteInput() }else if(mode == solveMode.rand){ rand() Reader.rerouteInput() } onecase() } if(t == 1 && mode != solveMode.real){ val dt = System.currentTimeMillis() - tn println("Time $dt ms ") } } fun rand(a:()->Unit){ this.rand = a } fun tc(id:Int = 0,a:()->Unit){ TC[id] = a } fun usetc(a:Int = 0 ){ this.tcNum = a this.mode = solveMode.tc } fun userand(){ this.mode = solveMode.rand } } fun debug(){} class BIT(val n:Int){ val A= IntArray(n+1) fun add(i:Int, v:Int){ var i = i; i++; while(i <= n){ A[i] = A[i] mp v; i += i and (-i)} } fun presum(i:Int): Int { var ret = 0; var i = i; i ++; while(i != 0){ ret = ret mp A[i]; i -= i and (-i)} return ret } fun sumquery(l:Int, r:Int):Int{ if(l > r) return 0 return presum(r) ms presum(l-1) } override fun toString(): String { return (0 until n).map { sumquery(it,it) }.joinToString(" ") } } class rsq(val arr:IntArray) { val ps = LongArray(arr.size + 1) constructor(arr:List):this(arr.toIntArray()){ } init{ for(i in 0 until arr.size){ ps[i+1] = ps[i] + arr[i] } } fun sumQuery(l:Int,r:Int):Long{ if(l > r || l >= arr.size || r < 0) return 0L val ll = maxOf(l,0) val rr = minOf(arr.lastIndex,r) + 1 return ps[rr] - ps[ll] } } fun IntArray.torsq(): rsq { return rsq(this) } fun List.torsq():rsq{ return rsq(this) } infix fun Long.modM(b:Long):Long{ return (this * b) % p } fun Int.additiveInverse():Int{ return if(this == 0) 0 else pI - this } fun intPowEXP(x:Int,e:Long,m:Int):Int{ var X = x var E =e var Y = 1 while(E > 0){ if(E % 2 == 0L){ X = ((1L * X * X) % m).toInt() E = E shr 1 }else{ Y = ((1L * X * Y) % m).toInt() E -= 1 } } return Y } fun pow(x:Long,e:Long,m:Long):Long{ var X = x var E =e var Y = 1L while(E > 0){ if(E % 2 == 0L){ X = (X * X) % m E /= 2 }else{ Y = (X * Y) % m E -= 1 } } return Y } fun Long.inverse():Long{ return pow(this,p-2,p) } class FACT{ companion object { var store = IntArray(0) var invStore = IntArray(0) var slowStore:IntArray = IntArray(0) fun preCal(upto:Int){ store = IntArray(upto+1) invStore = IntArray(upto + 1 ) store[0] = 1 invStore[0] = 1 for(i in 1..upto) { store[i] = store[i-1] mm i } invStore[upto] = store[upto].inverse() for(i in upto-1 downTo 1){ invStore[i] = invStore[i+1] mm (i+1) } } fun choose(n:Int,r:Int):Int{ if(r < 0 || r > n) return 0 val a = store[n] val b = invStore[n-r] val c = invStore[r] return (a mm b) mm c } fun bigChoose(n:Int,r:Int):Int{ var ret = 1 for(i in 0 until r){ ret = ret mm (n - i) } ret = ret mm (invStore[r]) return ret } fun veryBigChoose(n:Long,r:Int):Int{ var ret = 1 for(i in 0 until r){ ret = ret mm ((n - i) % pI).toInt() } ret = ret mm (invStore[r]) return ret } } } var tc = 0 fun gon(a:Any){ tc++ put("Case #${tc}: $a") } class rsqArrModded(val arr:IntArray){ val ps = IntArray(arr.size + 1) init{ for(i in 0 until arr.size){ ps[i+1] = ps[i] mp arr[i] } } fun sumQuery(l:Int,r:Int): Int { val ll = maxOf(l,0) val rr = minOf(arr.lastIndex,r) + 1 return ps[rr] ms ps[ll] } } const val singleCase = false fun main(){ solve.cases{ val str = getstr val n = str.size val ocount = ints(n) val leftcount = ints(n) val rightcount = ints(n) val equalcount = ints(n) val right = TreeSet() val equal = TreeSet() for(i in 0 until n){ if(str[i] == 'o'){ ocount[i] ++ }else if(str[i] == '<'){ leftcount[i] ++ }else if(str[i] == '>'){ rightcount[i] ++ right.add(i) }else if(str[i] == '='){ equalcount[i] ++ equal.add(i) } } val Oquery = ocount.torsq() val leftquery = leftcount.torsq() val rightquery = rightcount.torsq() val equalquery = equalcount.torsq() var ret = 0 val dp = BIT(n) var lastO = -1 var lastleft = -1 val pleasesetzero = Array(n){mint} for(i in 0 until n){ if(i in right){ continue } val nextright = right.ceiling(i) if(nextright != null){ val time = 2 * nextright - i if(time in 0 until n){ pleasesetzero[time].add(i) } } } for(i in 0 until n){ val c = str[i] for(k in pleasesetzero[i]){ dp.add(k, dp.sumquery(k,k).additiveInverse()) } if(c != '=' && c != '<' && c != '>'){ val canstart = Oquery.sumQuery(0, i-1) == 0L && leftquery.sumQuery(0,i-1) == 0L && equalquery.sumQuery(0,i-1) == 0L val canend = Oquery.sumQuery(i+1,n-1) == 0L && rightquery.sumQuery(i+1,n-1)== 0L && equalquery.sumQuery(i+1,n-1) == 0L var here = 0 if(canstart){ here = here mp 1 } var lower = 0 lower = maxOf(lower, lastO) lower = maxOf(lower, 2 * lastleft +1 - i) val upper = i-1 val old = equal.floor(upper) if(old != null && old >= lower){ val expect = old * 2 - i if(expect in lower..upper && equal.ceiling(expect) == old){ here = here mp dp.sumquery(expect,expect) } here = here mp dp.sumquery(old +1, upper) }else { here = here mp dp.sumquery(lower, upper) } dp.add(i,here) if(canend){ ret = ret mp (dp.sumquery(i,i)) } } if(c == 'o'){ lastO = i }else if( c== '<'){ lastleft = i } } // just dei dp gon(ret) } done() } /* 26 100 100 = exclude two ranges <> exclude one range o exclude one range . nothing happens ignore point exclusion for every two >, you bao ling it can start: no <, can end: no >, =, o */