Pearl Pendant Permutations

Little L is very wealthy and owns N pearls of each of K types. He wants to create a one‐of‐a‐kind pearl pendant by stringing pearls together. The length of the pendant is defined as the number of pearls in it. However, to show off his wealth, every pendant must include all K types of pearls.

More formally, for a pendant of length l (with 1 ≤ l ≤ N), we count it only if all K types appear in the sequence. Two pendants are considered distinct if the sequence (order) of pearls is different.

Your task is to compute the sum of the number of valid pendants for all lengths from 1 to N. Note that if N is less than K, it is impossible to have a pendant using all types, and the answer should be 0.

The answer can be written using the inclusion‐exclusion principle as follows:

\[ \text{Answer} = \sum_{l=\max(K,1)}^{N} \left( \sum_{j=0}^{K} (-1)^j \binom{K}{j} (K-j)^l \right) \mod 1234567891 \]

Since the answer can be very large, output it modulo 1234567891.

If N < K, output 0.

Can you help Little L and earn a share of his fortune?

inputFormat

The input consists of a single line containing two space‑separated integers: K and N, where:

• K represents the number of types of pearls.
• N represents the number of pearls available for each type, and also the maximum allowed length of the pendant.

outputFormat

Output a single integer — the total number of distinct valid pendants (that use all K types) for all lengths from 1 to N, taken modulo 1234567891.

sample

2 3

8