# Triangelfabriken
Implementera problemet som beskrivet

a,b,c = [int(input()) for _ in range(3)]

m = max(a,b,c)

if m > 90:
    print("Trubbig Triangel")
elif m == 90:
    print("Ratvinklig Triangel")
else:
    print("Spetsig Triangel")

# Truls Trubbel
Implementera problemet som beskrivet. Här kan det vara lite pilligt att fatta exakt vad man ska göra. Då hjälper det att kolla på samples.

s = input()

t = h = 0
for x in s:
    if x == "T":
        t += 1
    elif x == "H":
        h += 1
    
    if (t >= 11 or h >= 11) and abs(t-h) > 1:
        t = h = 0

print(f"{t}-{h}")

## Virus
Om viruset kan göra om $F$ till $H$, så kan varje bokstav från $F$ matchas upp med en från $H$. Till exempel: första bokstaven, a, i $F$ måste matchas med något a i $H$. Vilket a vill vi matcha med? Eftersom ordning spelar roll, så måste nästa bokstav i $F$ matchas med något till höger om a:et. Då visar det sig att vi lika gärna kan matcha a:et från $F$ med det vänstraste a:et från $H$. Vi kan sedan fortsätta så för b:et tills vi är färdiga.

Eftersom varje bokstav från $F$ kan matchas med en bokstav från $H$ är svaret Ja.

s = input()
t = input()
r = 0
for c in s:
    while r < len(t) and t[r] != c:
        r += 1
    if r == len(t):
        print("nej")
        exit()
    r += 1
print("ja")

# Siffrids siffersumma
### Största
Beräkna först siffersumman. Placera sedan så många nior som möjligt i början. När du inte kan placera nior längre kan du placera siffersumman du har kvar.

### Minsta
Här gäller nästa exakta motsatsen: vi vill placera så mycket som möjligt emot slutet av talet. Vi måste dock ha med en etta i början, annars får talet för få siffror. Notera specialfall såsom 949, där det istället blir en fyra i början.

### Implementation
Det finns två rimliga sätt att implementera detta: antingen att du arbetar med strängar eller ints. Den enklaste implementationen vi hittat är med ints, men strängar funkar också fint.

def get_min(dsum, length):
    dsum -= 1 # Spara en etta så att den får lika många siffror
    ret = 0
    for i in range(length-1):
        ret += min(dsum, 9) * (10**i)
        dsum -= min(dsum, 9)
    ret += (1+dsum) * (10**(length-1))
    return ret

def get_max(dsum, length):
    ret = 0
    for i in range(length):
        ret += min(dsum, 9) * (10**(length-i-1))
        dsum -= min(dsum, 9)
    return ret

n = input()
dsum = sum([int(d) for d in n])
length = len(n)
print(get_min(dsum, length), get_max(dsum, length))

# Miniräknaren
Ett allmänt tips inom problemlösning är att ibland överväga att "tänka baklänges". I detta problemet är det svårt tänka på det om man börjar på $0$ och ska ta sig till $N$. Låt oss istället vända på det. Vi börjar på $N$ och ska ta oss till $0$. Vi kan antingen subtrahera ett tal i $[0, M-1]$ eller dividera med $M$ och talet just nu är delbart med $M$.

### $M=2$
Intuitivt är det mycket bättre att dividera än att subtrahera. Så vi dividerar om vi kan, annars subtraherar vi.

n = int(input())
m = int(input())

ans = 0
while n:
    if n % 2 == 1:
        n -= 1
        ans += 1

    if n:
        n >>= 1
        ans += 1

print(ans)

### Allmäna fallet
Det är frestande att tänka att detta alltid funkar. Om talet är delbart med $M$, dela med $M$, annars ta bort så att talet blir delbart med $M$. Detta funkar nästan! Ett motexempel är $N=4, M=3$.
Då säger vår algoritm att vi ska ta $-1, \mathbin{/}3, -1$. Men istället kan vi göra $-2, -2$. Intuitivt så sker detta bara för små tal. Det går att bevisa att om vårt tal just nu är större än $2\cdot (m-1)$, så är ovanstående algoritm optimal. Om talet är $\leq 2\cdot (m-1)$, så kan vi lägga till $2$ på svaret och bryta loopen.

n = int(input())
m = int(input())
ans = 0
while n > 0:
    if m <= n <= 2*m-2:
        ans += 2
        break
    if n%m == 0:
        n //= m
    else:
        n -= n%m
    ans += 1
print(ans)

### Allmän kommentar
$74$ personer fick $3$ poäng på miniräknaren, medan $8$ fick $5$ poäng. Självklart är en del av dessa $3$-poängarna säkert från en $\mathcal{O}(N)$ dp, men troligtvis så gissade många med den giriga algoritmen och misslyckades att hitta specialfallet. Att vi inte hade med ett exempelfall som gav fel svar var med mening. I en riktig tävling med en onlinedomare är det bra strategi att koda upp och skicka in det. Men i skolkvalet borde man testa sina lösningar mer- det var lite därför vi hade subtask $M = 3, N \leq 10$. Om man tog och testade lite för hand, som den uppmuntrade, märker man väldigt snabbt specialfallet.

Hur generaliserar detta till "riktiga tävlingar"? På IOI (tävlingsprogrammerings-OS) kan det komma uppgifter där liknande giriga stragier verkar korrekta. Men då kan det ta en timme att koda upp, så då är det bra att lägga åtminstone ett antal minuter att verkligen övertyga sig själv om lösningens korrekthet.

# Trollkarlen Theodor
Först måste vi avgöra optimala strategin för Theodor. Om man testar några exempel för hand kan man insé att denna är att alltid sikta på monstret med mest liv kvar. Om man implementerar detta löser man testfallgrupp $2$.

n, s, a = map(int, input().split())
life = [int(i) for i in input().split()]

def any_alive(life):
    return any(i > 0 for i in life)

ans = 0
while any_alive(life):
    for i in range(n):
        life[i] -= a
    most_life_index = 0
    for i in range(n):
        if life[i] > life[most_life_index]:
            most_life_index = i
    life[most_life_index] -= s
    ans += 1
print(ans)

Varför ger inte detta full poäng? Det värsta fallet visar sig vara när $S$ och $A$ är jättesmå. Om alla monster har jättemycket liv behöver loopen köra jättemånga gånger, och det blir för långsamt.

Istället behöver vi byta perspektiv. Låt säga att någon sa "det går att besegra armén med $10$ explosioner". Då är det jättelätt att kolla om detta stämmer i $\mathcal{O}(N)$: det går att göra med en enda loop. Det stämmer även att om det går att besegra armén med ett visst antal explosioner går det med fler. Om det inte går, så går det inte med färre. Det ger att vi kan binärsöka över antalet explosioner. Denna idén är känd som "binärsökning över svaret". Detta ger i slutändan $\mathcal{O}(N\log{}(N\cdot 10^9))$.

n, s, a = map(int, input().split())
h = list(map(int, input().split()))
lo = 0
hi = n*10**9
while lo < hi-1:
    mid = (lo+hi) // 2
    need = 0
    for x in h:
        hp_left = x - mid * a
        if hp_left > 0:
            # Computes ceil(hp_left/s)
            need += (hp_left+s-1) // s
    if need <= mid:
        hi = mid
    else:
        lo = mid
print(hi)

Om du kodar i C++ får du akta dig för overflow: $mid \cdot a$ kan bli väldigt stort. Du kan antingen använda __int128_t, eller sätta $\mathit{hi}$ till exakt $10^{10}$. Om $\mathit{hi} > 2 \cdot 10^{10}$ får du overflow. Alternativt kan du sätta $\mathit{hi}$ till $\frac{10^{12}}{a}$ (där $10^{12}$ är ett godtyckligt, stort tal).

# Theodor, Trollkarlen
## Testfallsgrupp $1$
Här räcker det att ta en lösning från Trollkarlen Theodor och generera alla möjliga monster-arméer, och sedan simulera hur lång tid det tar. Lösningen behöver inte vara snabb alls, så länge den är korrekt.

## Testfallsgrupp $2$
Man kan antingen lösa denna med kombinatorik eller DP. Vi kommer visa DP-lösningen. Vi gör detta genom att skapa en rekursiv funktion som testar hur mycket liv varje monster ska ha, och räknar hur många explosioner som krävs för att besegra det monstret. Vi vill då räkna antalet arméer som har $N$ monster och kräver exakt $K$ explosioner att besegra.

MOD = int(1e9 + 7)

dp = [[-1 for _ in range(100)] for _ in range(100)]
def count(i, blasts):
    if blasts > k:
        return 0
    if i == n:
        return 1 if blasts == k else 0

    if dp[i][blasts] != -1:
        return dp[i][blasts]

    ret = 0
    hp = 1
    while True:
        new_blasts = (hp - 1) // s + 1
        if blasts + new_blasts > k:
            break
        ret += count(i + 1, blasts + new_blasts)
        ret %= MOD
        hp += 1

    dp[i][blasts] = ret
    return ret
    
n, k, s, a = map(int, input().split())

print(count(0, 0))

## Testfallsgrupp $3$
Det är lätt att tro att ovanstående lösning fungerar för $A \neq 0$ med väldigt små förändringar. Tyvärr stämmer inte detta.

Betrakta följande fall: $N=2, K=2, S=0, A=1$. Om vi kör ovanstående lösning, så kommer armén $(2,2)$ att räknas som att den tar noll explosioner, medan den tar två. I allmänhet blir det svårt att effektivt räkna exakt hur många explosioner som krävs. Istället byter vi perspektiv. Just nu räknar vi antalet arméer som besegras på exakt $K$ explosioner. Istället räknar vi $\mathcal{F}(u)$: Antalet arméer som besegras på $u$ **eller färre** explosioner. Så blir svaret $\mathcal{F}(K)-\mathcal{F}(K-1)$.

Med detta kan vi göra en DP. För att snabba upp kan vi också insé att alla minster med liv inom $[1, AK]$ dör direkt, så det finns ingen poäng att loopa över de. Om den har mer liv spelar det inte roll exakt hur mycket, utan bara hur många explosioner som krävs. Om man implementerar detta ordentligt får man $60$ poäng eftersom koden kör i $\mathcal{O}(
NK^2)$.

MOD = int(1e9 + 7)

dp = []
n, k, s, a = map(int, input().split())

def count(i, blasts_left, k):
    if i == n:
        return 1

    # Reference for dp
    if dp[i][blasts_left] != -1:
        return dp[i][blasts_left]

    ret = 0

    # Calculate global damage
    global_damage = k * a
    # Monsters with health [0, global_damage] are already dead
    ret += global_damage * count(i + 1, blasts_left, k)
    ret %= MOD

    for new_blasts in range(1, k + 1):
        if blasts_left - new_blasts < 0:
            break
        ret += s * count(i + 1, blasts_left - new_blasts, k)
        ret %= MOD

    dp[i][blasts_left] = ret
    return ret

def F(k):
    global dp
    dp = [[-1 for _ in range(350)] for _ in range(350)]
    return count(0, k, k)

ans = (F(k) - F(k-1)) % MOD
print((ans + MOD) % MOD)

## Testfallgrupp $4$
För att lösa denna gruppen kan vi göra normal DP-optimering av förra lösningen. Vi skriver ut vår DP-relation:

$$\mathit{DP}[i][k]=ak \cdot \mathit{DP}[i-1][k] +s \left(\mathit{DP}[i-1][k-1] + \mathit{DP}[i-1][k-2] + \dots +\mathit{DP}[i-1][0] \right).$$

Delen som får lösningen att ta $\mathcal{O}(NK^2)$ tid istället för $\mathcal{O}(NK)$ är alltså summan där inne. Om vi evaluerar vår DP i en trevlig ordningen med bottom-up och bygger en prefixsumma över $\mathit{DP}[i-1]$ när vi beräknar $\mathit{DP}[i]$, så går det i $\mathcal{O}(NK)$.

MOD = int(1e9 + 7)

n, k, s, a = map(int, input().split())

def count_bottomup(k):
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1

    global_damage = k * a
    for i in range(1, n + 1):
        for j in range(k + 1):
            dp[i][j] += dp[i - 1][j] * global_damage
            dp[i][j] %= MOD

        for j in range(1, k + 1):
            dp[i - 1][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % MOD

        for j in range(1, k + 1):
            dp[i][j] += s * dp[i - 1][j - 1]
            dp[i][j] %= MOD

    ret = 0
    for i in range(k + 1):
        ret += dp[n][i]
    return ret % MOD

print(((count_bottomup(k) - count_bottomup(k-1)) % MOD + MOD) % MOD)

## Fullösning
Tyvärr har vi nått en vanlig "mur" för DP-lösningar: lösningen har $\mathcal{O}(NK)$ states och $\mathcal{O}(1)$ transitions per state. För att optimera lösningen hade vi behövt bli av med state. Men det känns omöjligt att göra. Istället kommer vi att lösa det med kombinatorik. Precis som innan är målet att beräkna $\mathcal{F}(u)$, men nu i $\mathcal{O}(N+K)$.

Vi börjar med att loopa över hur många unika monster som vi ska sikta på. Vi vill då räkna hur många sätt det finns att tilldela liv om vi kommer att sikta på exakt $i$ unika monster. Vi testar varje $i$ mellan $0$ och $\min(N,u)$. Vi måste först hantera ordningar- det finns ${N \choose i}$ sätt att välja dessa. För varje monster vi inte siktar på finns det $A \cdot u$ möjliga liv, och det finns $N-i$ sådana. Vi måste nu kunna snabbt beräkna hur många sätt vi kan fördela explosioner mellan monstrena. Man kan gräva in sig i att räkna partitioner, men det finns ett lättare sätt. Låt $E_j$ vara antalet explosioner som monster j behöver för att besegras på max u explosioner för alla $j \in [0, i]$. Enligt tidigare så är $E_j \geq 1$, givet detta vill vi nu bestämma antalet sätt så att summan över alla $E_j$ är mindre eller lika med $u$, vilket betyder att följande måste hålla:

$$\sum_{j=0}^i E_j \leq u.$$

För att göra detta börjar vi med att skjuta varje monster en gång, vilket kräver $i$ explosioner. Nu så har vi inte längre kravet att $E_j \geq 1$ så vi kan använda [stars and bars](https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)) för att räkna antalet sätt. Stars and bars låter oss inte räkna antalet sätt $\leq u$, utan istället $=M$ för något $M$. Stars and bars ger då att $\sum_{j=0}^i E_j = M$ går att göra på ${M+i-1} \choose {i-1}$ sätt. Detta får vi genom att vi har $M$ stycken stjärnor, en för varje explosion och $i-1$ stycken bars, för att dela upp explosionerna mellan våra $i$ monster. Bars används för att dela upp våra $M$ explosioner i $i$ olika grupper, en för varje monster. "Theorem two" från artikeln om stars and bars ger därmed att antalet sätt där vissa monster kan få noll explosioner är lika med ${M+i-1} \choose {i-1}$. Du kan läsa wikipedia-artikeln för bevis att detta stämmer. Om vi nu låter $M$ gå från $0$ till $u-i$ så kan vi räkna antalet sätt $\leq u$, vilket ger

$$\sum_{M=0}^{u-i} {{M+i-1} \choose {i-1}}.$$

Med [Hockey-stick identiteten](https://en.wikipedia.org/wiki/Hockey-stick_identity) kan det förenklas till ${(u-i)+(i)} \choose i$=$u \choose i$.

Notera också att när vi väl bestämt antalet explosioner $E$ per monster vi siktar på, så kan det ha liv inom intervallet $[E,E+S)$. Detta ger en faktor $S^i$ till svaret.

Allt som allt får vi alltså att
$$\mathcal{F}(u)=\sum_{i=0}^{min(N,u)} {N \choose i}(A\cdot u)^{N-i}{u \choose i}S^i.$$

Alla faktorer beskrivs ovanför, så om något är otydligt, titta tidigare i beskrivningen.

För att kunna beräkna ${n \choose k}$ snabbt behöver vi också förberäkna fakulteter och invers-fakulteter modulo $(10^9+7)$. Notera att följande kod inte är jättenoga med att använda modulo hela tiden. Detta är okej eftersom Pythons tal inte kan overflowa, men samma kod hade inte fått rätt svar i C++. Notera att vi ljög lite om komplexiteten. Det läggs till en logfaktor på grund av pow-anropen. Dessa går att bli av med.

MOD = 10**9+7
MAXN = 2*10**5+5

fac = [0] * MAXN
inv = [0] * MAXN
t = 1
for i in range(MAXN):
    fac[i] = t
    t *= (i+1)
    t %= MOD
inv[MAXN-1] = pow(fac[MAXN-1], MOD-2, MOD)
for i in range(MAXN-1)[::-1]:
    inv[i] = (inv[i+1] * (i+1))%MOD

def binomial(i, j):
    if i < 0 or j < 0 or i < j:
        return 0
    return (((fac[i]*inv[j])%MOD)*inv[i-j])%MOD

n,k,s,a = map(int,input().split())

def f(u):
    ans = 0

    for i in range(min(n, u)+1):
        ans += binomial(n,i)*pow(a*u, n-i, MOD)*binomial(u, i)*pow(s,i, MOD) % MOD
        ans %= MOD
    return ans

print((f(k)-f(k-1))%MOD)