Problem B: Time Complexity

ICPC World Finals 1日目

プログラミングコンテストではプログラムの実行時間を把握する事が重要だ。 実行時間の見積もりを誤り、 時間制限をオーバーしてしまうコードを書いてしまうと、 そのぶん時間をロスしてしまう。 ICPCのようにコンピュータが1台しか使えないチーム戦ではなおさらである。

そこで、ICPC World Finalsを前に控えたティー氏はプログラムの実行時間を暗算で求める訓練を始めることにした。 「logは定数のようなもの」なので、まずは多項式に取り組むとしよう。

問題

ある問題の答えを計算するプログラムと、それを実行するコンピュータがある。 問題の入力を表す正整数$n$、 入力$n$に応じてプログラム中で実行される命令の数を表す多項式$f(n)$、 コンピュータの1命令の実行時間$T$[ナノ秒]（=$10^{-9}$[秒]）が与えられる。 多項式$f(n)$の回数だけ命令を実行した時のプログラムの総実行時間が1秒「以下」であるかを判定し、 1秒「以下」であるならば総実行時間を求めよ。

入力

n T
f(n)

1行目に 問題の入力を表す正整数$n$と 1命令の実行時間[ナノ秒]を表す整数$T$が空白区切りで与えられる。 2行目に実行される命令の数を表す多項式$f(n)$が与えられる。

多項式$f(n)$は以下のBNFで表される。

<poly> ::= <poly> "+" <mono> | <mono>
<mono> ::= "n^" <num>
<num> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

ここで各単項式n^kは、$n$の$k$乗を表す。

出力

プログラムの総実行時間が1秒「以下」である場合には総実行時間を[ナノ秒]単位で、1秒を「超過」する場合には"TLE"を1行に出力せよ。

制約

• $1 \leq n \leq 10^{9}(= 1000000000)$
• $1 \leq T \leq 10^{9}(= 1000000000)$
• 多項式$f(n)$の次数は0以上9以下、単項式の数は1以上10以下

入出力例

入力1

100 100
n^1+n^2+n^3

出力1

101010000

総実行時間は$(100^{1} + 100^{2} + 100^{3}) \times 100$[ナノ秒]である。

入力2

1000 1
n^3+n^0

出力2

TLE

総実行時間は$1000^{3} + 1000^{0} = 10^{9}+1$[ナノ秒]であり、1[秒]を超えてしまう。

入力3

100000000 100000000
n^3

出力3

TLE

総実行時間は$(10^{8})^{3} \times 10^{8} = 10^{32}$[ナノ秒]である。