





_a 						=      range(2, 20 + 1)
_a 						=      [10**k for k in range(ks[-1] + 1)]
_a 						=      {}





def lowerCAmelCase__(__snake_case       ,__snake_case       ,__snake_case       ,__snake_case							)				->      int:







	'''simple docstring'''







	lowerCamelCase__								=		sum(a_i[j] for j in range(__snake_case       ,len(__snake_case							)							)							)
	lowerCamelCase__								=		sum(a_i[j] * base[j] for j in range(min(len(__snake_case							)       ,__snake_case							)							)							)

	lowerCamelCase__				,	lowerCamelCase__								=		0, 0
	lowerCamelCase__								=		n - i

	lowerCamelCase__								=		memo.get(__snake_case							)

	if sub_memo is not None:
		lowerCamelCase__								=		sub_memo.get(__snake_case							)

		if jumps is not None and len(__snake_case							) > 0:
			# find and make the largest jump without going over
			lowerCamelCase__								=		-1
			for _k in range(len(__snake_case							) - 1       ,-1       ,-1							):
				if jumps[_k][2] <= k and jumps[_k][1] <= max_dn:
					lowerCamelCase__								=		_k
					break

			if max_jump >= 0:
				lowerCamelCase__				,	lowerCamelCase__				,	lowerCamelCase__								=		jumps[max_jump]
				# since the difference between jumps is cached, add c
				lowerCamelCase__								=		diff + c
				for j in range(min(__snake_case       ,len(__snake_case							)							)							):
					lowerCamelCase__				,	lowerCamelCase__								=		divmod(__snake_case       ,10							)
				if new_c > 0:
					add(__snake_case       ,__snake_case       ,__snake_case							)

		else:
			lowerCamelCase__								=		[]
	else:
		lowerCamelCase__								=		{c: []}
		lowerCamelCase__								=		sub_memo

	if dn >= max_dn or c + diff >= base[k]:
		return diff, dn

	if k > ks[0]:
		while True:
			# keep doing smaller jumps
			lowerCamelCase__				,	lowerCamelCase__								=		next_term(__snake_case       ,k - 1       ,i + dn       ,__snake_case							)
			diff += _diff
			dn += terms_jumped

			if dn >= max_dn or c + diff >= base[k]:
				break
	else:
		# would be too small a jump, just compute sequential terms instead
		lowerCamelCase__				,	lowerCamelCase__								=		compute(__snake_case       ,__snake_case       ,i + dn       ,__snake_case							)
		diff += _diff
		dn += terms_jumped

	lowerCamelCase__								=		sub_memo[c]

	# keep jumps sorted by # of terms skipped
	lowerCamelCase__								=		0
	while j < len(__snake_case							):
		if jumps[j][1] > dn:
			break
		j += 1

	# cache the jump for this value digitsum(b) and c
	sub_memo[c].insert(__snake_case       ,(diff, dn, k)							)
	return (diff, dn)





def lowerCAmelCase__(__snake_case       ,__snake_case       ,__snake_case       ,__snake_case							)				->      Dict:







	'''simple docstring'''







	if i >= n:
		return 0, i
	if k > len(__snake_case							):
		a_i.extend([0 for _ in range(k - len(__snake_case							)							)]							)

	# note: a_i -> b * 10^k + c
	# ds_b -> digitsum(b)
	# ds_c -> digitsum(c)
	lowerCamelCase__								=		i
	lowerCamelCase__				,	lowerCamelCase__				,	lowerCamelCase__								=		0, 0, 0
	for j in range(len(__snake_case							)							):
		if j >= k:
			ds_b += a_i[j]
		else:
			ds_c += a_i[j]

	while i < n:
		i += 1
		lowerCamelCase__								=		ds_c + ds_b
		diff += addend
		lowerCamelCase__								=		0
		for j in range(__snake_case							):
			lowerCamelCase__								=		a_i[j] + addend
			lowerCamelCase__				,	lowerCamelCase__								=		divmod(__snake_case       ,10							)

			ds_c += a_i[j]

		if addend > 0:
			break

	if addend > 0:
		add(__snake_case       ,__snake_case       ,__snake_case							)
	return diff, i - start_i





def lowerCAmelCase__(__snake_case       ,__snake_case       ,__snake_case							)				->      Tuple:







	'''simple docstring'''







	for j in range(__snake_case       ,len(__snake_case							)							):
		lowerCamelCase__								=		digits[j] + addend
		if s >= 10:
			lowerCamelCase__				,	lowerCamelCase__								=		divmod(__snake_case       ,10							)
			lowerCamelCase__								=		addend // 10 + quotient
		else:
			lowerCamelCase__								=		s
			lowerCamelCase__								=		addend // 10

		if addend == 0:
			break

	while addend > 0:
		lowerCamelCase__				,	lowerCamelCase__								=		divmod(__snake_case       ,10							)
		digits.append(__snake_case							)





def lowerCAmelCase__(__snake_case = 10**15							)				->      int:







	'''simple docstring'''







	lowerCamelCase__								=		[1]
	lowerCamelCase__								=		1
	lowerCamelCase__								=		0
	while True:
		lowerCamelCase__				,	lowerCamelCase__								=		next_term(__snake_case       ,20       ,i + dn       ,__snake_case							)
		dn += terms_jumped
		if dn == n - i:
			break

	lowerCamelCase__								=		0
	for j in range(len(__snake_case							)							):
		a_n += digits[j] * 10**j
	return a_n


if __name__ == "__main__":
			print(f"""{solution() = }""")










import itertools
import random
import unittest

import numpy as np

from transformers import is_speech_available
from transformers.testing_utils import require_torch, require_torchaudio

from ...test_sequence_feature_extraction_common import SequenceFeatureExtractionTestMixin


if is_speech_available():
			from transformers import SpeechaTextFeatureExtractor

_a 						=      random.Random()





def lowerCAmelCase__(__snake_case       ,__snake_case=1.0       ,__snake_case=None       ,__snake_case=None							)				->      List[Any]:







	'''simple docstring'''







	if rng is None:
		lowerCamelCase__								=		global_rng

	lowerCamelCase__								=		[]
	for batch_idx in range(shape[0]							):
		values.append([]							)
		for _ in range(shape[1]							):
			values[-1].append(rng.random() * scale							)

	return values






@require_torch
@require_torchaudio
class 					__A    (    unittest.TestCase ):

			'''simple docstring'''







			def __init__(    self       ,  __lowerCAmelCase       ,  __lowerCAmelCase=7       ,  __lowerCAmelCase=4_0_0       ,  __lowerCAmelCase=2_0_0_0       ,  __lowerCAmelCase=2_4       ,  __lowerCAmelCase=2_4       ,  __lowerCAmelCase=0.0       ,  __lowerCAmelCase=1_6_0_0_0       ,  __lowerCAmelCase=True       ,  __lowerCAmelCase=True       ,  ):



				'''simple docstring'''







				lowerCamelCase__								=		parent
				lowerCamelCase__								=		batch_size
				lowerCamelCase__								=		min_seq_length
				lowerCamelCase__								=		max_seq_length
				lowerCamelCase__								=		(self.max_seq_length - self.min_seq_length) // (self.batch_size - 1)
				lowerCamelCase__								=		feature_size
				lowerCamelCase__								=		num_mel_bins
				lowerCamelCase__								=		padding_value
				lowerCamelCase__								=		sampling_rate
				lowerCamelCase__								=		return_attention_mask
				lowerCamelCase__								=		do_normalize





			def 		__lowerCamelCase				(    self							):



				'''simple docstring'''







				return {
				    "feature_size": self.feature_size,
				    "num_mel_bins": self.num_mel_bins,
				    "padding_value": self.padding_value,
				    "sampling_rate": self.sampling_rate,
				    "return_attention_mask": self.return_attention_mask,
				    "do_normalize": self.do_normalize,
				}





			def 		__lowerCamelCase				(    self       ,  __lowerCAmelCase=False       ,  __lowerCAmelCase=False							):



				'''simple docstring'''







				def _flatten(__lowerCAmelCase							):
					return list(itertools.chain(*__lowerCAmelCase							)							)

				if equal_length:
					lowerCamelCase__								=		[floats_list((self.max_seq_length, self.feature_size)							) for _ in range(self.batch_size							)]
				else:
					# make sure that inputs increase in size
					lowerCamelCase__								=		[
					    floats_list((x, self.feature_size)							)
					    for x in range(self.min_seq_length       ,  self.max_seq_length       ,  self.seq_length_diff							)
					]
				if numpify:
					lowerCamelCase__								=		[np.asarray(__lowerCAmelCase							) for x in speech_inputs]
				return speech_inputs






@require_torch
@require_torchaudio
class 					__A    (    lowerCAmelCase			,				unittest.TestCase ):

			'''simple docstring'''







			lowerCAmelCase_							     =						SpeechaTextFeatureExtractor if is_speech_available() else None





			def 		__lowerCamelCase				(    self							):



				'''simple docstring'''







				lowerCamelCase__								=		SpeechaTextFeatureExtractionTester(self							)





			def 		__lowerCamelCase				(    self       ,  __lowerCAmelCase							):



				'''simple docstring'''







				self.assertTrue(np.all(np.mean(__lowerCAmelCase       ,  axis=0							) < 1E-3							)							)
				self.assertTrue(np.all(np.abs(np.var(__lowerCAmelCase       ,  axis=0							) - 1							) < 1E-3							)							)





			def 		__lowerCamelCase				(    self							):



				'''simple docstring'''







				lowerCamelCase__								=		self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()							)
				# create three inputs of length 800, 1000, and 1200
				lowerCamelCase__								=		[floats_list((1, x)							)[0] for x in range(8_0_0       ,  1_4_0_0       ,  2_0_0							)]
				lowerCamelCase__								=		[np.asarray(__lowerCAmelCase							) for speech_input in speech_inputs]

				# Test feature size
				lowerCamelCase__								=		feature_extractor(__lowerCAmelCase       ,  padding=__lowerCAmelCase       ,  return_tensors='''np'''							).input_features
				self.assertTrue(input_features.ndim == 3							)
				self.assertTrue(input_features.shape[-1] == feature_extractor.feature_size							)

				# Test not batched input
				lowerCamelCase__								=		feature_extractor(speech_inputs[0]       ,  return_tensors='''np'''							).input_features
				lowerCamelCase__								=		feature_extractor(np_speech_inputs[0]       ,  return_tensors='''np'''							).input_features
				self.assertTrue(np.allclose(__lowerCAmelCase       ,  __lowerCAmelCase       ,  atol=1E-3							)							)

				# Test batched
				lowerCamelCase__								=		feature_extractor(__lowerCAmelCase       ,  return_tensors='''np'''							).input_features
				lowerCamelCase__								=		feature_extractor(__lowerCAmelCase       ,  return_tensors='''np'''							).input_features
				for enc_seq_a, enc_seq_a in zip(__lowerCAmelCase       ,  __lowerCAmelCase							):
					self.assertTrue(np.allclose(__lowerCAmelCase       ,  __lowerCAmelCase       ,  atol=1E-3							)							)

				# Test 2-D numpy arrays are batched.
				lowerCamelCase__								=		[floats_list((1, x)							)[0] for x in (8_0_0, 8_0_0, 8_0_0)]
				lowerCamelCase__								=		np.asarray(__lowerCAmelCase							)
				lowerCamelCase__								=		feature_extractor(__lowerCAmelCase       ,  return_tensors='''np'''							).input_features
				lowerCamelCase__								=		feature_extractor(__lowerCAmelCase       ,  return_tensors='''np'''							).input_features
				for enc_seq_a, enc_seq_a in zip(__lowerCAmelCase       ,  __lowerCAmelCase							):
					self.assertTrue(np.allclose(__lowerCAmelCase       ,  __lowerCAmelCase       ,  atol=1E-3							)							)





			def 		__lowerCamelCase				(    self							):



				'''simple docstring'''







				lowerCamelCase__								=		self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()							)
				lowerCamelCase__								=		[floats_list((1, x)							)[0] for x in range(8_0_0       ,  1_4_0_0       ,  2_0_0							)]

				lowerCamelCase__								=		['''longest''', '''max_length''', '''do_not_pad''']
				lowerCamelCase__								=		[None, 1_6, None]
				for max_length, padding in zip(__lowerCAmelCase       ,  __lowerCAmelCase							):
					lowerCamelCase__								=		feature_extractor(
					    __lowerCAmelCase       ,  padding=__lowerCAmelCase       ,  max_length=__lowerCAmelCase       ,  return_attention_mask=__lowerCAmelCase							)
					lowerCamelCase__								=		inputs.input_features
					lowerCamelCase__								=		inputs.attention_mask
					lowerCamelCase__								=		[np.sum(__lowerCAmelCase							) for x in attention_mask]

					self._check_zero_mean_unit_variance(input_features[0][: fbank_feat_lengths[0]]							)
					self._check_zero_mean_unit_variance(input_features[1][: fbank_feat_lengths[1]]							)
					self._check_zero_mean_unit_variance(input_features[2][: fbank_feat_lengths[2]]							)





			def 		__lowerCamelCase				(    self							):



				'''simple docstring'''







				lowerCamelCase__								=		self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()							)
				lowerCamelCase__								=		[floats_list((1, x)							)[0] for x in range(8_0_0       ,  1_4_0_0       ,  2_0_0							)]

				lowerCamelCase__								=		['''longest''', '''max_length''', '''do_not_pad''']
				lowerCamelCase__								=		[None, 1_6, None]
				for max_length, padding in zip(__lowerCAmelCase       ,  __lowerCAmelCase							):
					lowerCamelCase__								=		feature_extractor(
					    __lowerCAmelCase       ,  max_length=__lowerCAmelCase       ,  padding=__lowerCAmelCase       ,  return_tensors='''np'''       ,  return_attention_mask=__lowerCAmelCase							)
					lowerCamelCase__								=		inputs.input_features
					lowerCamelCase__								=		inputs.attention_mask
					lowerCamelCase__								=		[np.sum(__lowerCAmelCase							) for x in attention_mask]

					self._check_zero_mean_unit_variance(input_features[0][: fbank_feat_lengths[0]]							)
					self.assertTrue(input_features[0][fbank_feat_lengths[0] :].sum() < 1E-6							)
					self._check_zero_mean_unit_variance(input_features[1][: fbank_feat_lengths[1]]							)
					self.assertTrue(input_features[0][fbank_feat_lengths[1] :].sum() < 1E-6							)
					self._check_zero_mean_unit_variance(input_features[2][: fbank_feat_lengths[2]]							)





			def 		__lowerCamelCase				(    self							):



				'''simple docstring'''







				lowerCamelCase__								=		self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()							)
				lowerCamelCase__								=		[floats_list((1, x)							)[0] for x in range(8_0_0       ,  1_4_0_0       ,  2_0_0							)]
				lowerCamelCase__								=		feature_extractor(
				    __lowerCAmelCase       ,  padding='''max_length'''       ,  max_length=4       ,  truncation=__lowerCAmelCase       ,  return_tensors='''np'''       ,  return_attention_mask=__lowerCAmelCase       ,  )
				lowerCamelCase__								=		inputs.input_features
				lowerCamelCase__								=		inputs.attention_mask
				lowerCamelCase__								=		np.sum(attention_mask == 1       ,  axis=1							)

				self._check_zero_mean_unit_variance(input_features[0, : fbank_feat_lengths[0]]							)
				self._check_zero_mean_unit_variance(input_features[1]							)
				self._check_zero_mean_unit_variance(input_features[2]							)





			def 		__lowerCamelCase				(    self							):



				'''simple docstring'''







				lowerCamelCase__								=		self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()							)
				lowerCamelCase__								=		[floats_list((1, x)							)[0] for x in range(8_0_0       ,  1_4_0_0       ,  2_0_0							)]
				lowerCamelCase__								=		feature_extractor(
				    __lowerCAmelCase       ,  padding='''longest'''       ,  max_length=4       ,  truncation=__lowerCAmelCase       ,  return_tensors='''np'''       ,  return_attention_mask=__lowerCAmelCase       ,  )
				lowerCamelCase__								=		inputs.input_features
				lowerCamelCase__								=		inputs.attention_mask
				lowerCamelCase__								=		np.sum(attention_mask == 1       ,  axis=1							)

				self._check_zero_mean_unit_variance(input_features[0, : fbank_feat_lengths[0]]							)
				self._check_zero_mean_unit_variance(input_features[1, : fbank_feat_lengths[1]]							)
				self._check_zero_mean_unit_variance(input_features[2]							)

				# make sure that if max_length < longest -> then pad to max_length
				self.assertEqual(input_features.shape       ,  (3, 4, 2_4)							)

				lowerCamelCase__								=		[floats_list((1, x)							)[0] for x in range(8_0_0       ,  1_4_0_0       ,  2_0_0							)]
				lowerCamelCase__								=		feature_extractor(
				    __lowerCAmelCase       ,  padding='''longest'''       ,  max_length=1_6       ,  truncation=__lowerCAmelCase       ,  return_tensors='''np'''       ,  return_attention_mask=__lowerCAmelCase       ,  )
				lowerCamelCase__								=		inputs.input_features
				lowerCamelCase__								=		inputs.attention_mask
				lowerCamelCase__								=		np.sum(attention_mask == 1       ,  axis=1							)

				self._check_zero_mean_unit_variance(input_features[0, : fbank_feat_lengths[0]]							)
				self._check_zero_mean_unit_variance(input_features[1, : fbank_feat_lengths[1]]							)
				self._check_zero_mean_unit_variance(input_features[2]							)

				# make sure that if max_length < longest -> then pad to max_length
				self.assertEqual(input_features.shape       ,  (3, 6, 2_4)							)





			def 		__lowerCamelCase				(    self							):



				'''simple docstring'''







				import torch

				lowerCamelCase__								=		self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()							)
				lowerCamelCase__								=		np.random.rand(1_0_0       ,  3_2							).astype(np.floataa							)
				lowerCamelCase__								=		np_speech_inputs.tolist()

				for inputs in [py_speech_inputs, np_speech_inputs]:
					lowerCamelCase__								=		feature_extractor.pad([{'''input_features''': inputs}]       ,  return_tensors='''np'''							)
					self.assertTrue(np_processed.input_features.dtype == np.floataa							)
					lowerCamelCase__								=		feature_extractor.pad([{'''input_features''': inputs}]       ,  return_tensors='''pt'''							)
					self.assertTrue(pt_processed.input_features.dtype == torch.floataa							)





			def 		__lowerCamelCase				(    self       ,  __lowerCAmelCase							):



				'''simple docstring'''







				from datasets import load_dataset

				lowerCamelCase__								=		load_dataset('''hf-internal-testing/librispeech_asr_dummy'''       ,  '''clean'''       ,  split='''validation'''							)
				# automatic decoding with librispeech
				lowerCamelCase__								=		ds.sort('''id'''							).select(range(__lowerCAmelCase							)							)[:num_samples]['''audio''']

				return [x["array"] for x in speech_samples]





			def 		__lowerCamelCase				(    self							):



				'''simple docstring'''







				lowerCamelCase__								=		np.array([
				    -1.5745, -1.7713, -1.7020, -1.6069, -1.2250, -1.1105, -0.9072, -0.8241,
				    -1.2310, -0.8098, -0.3320, -0.4101, -0.7985, -0.4996, -0.8213, -0.9128,
				    -1.0420, -1.1286, -1.0440, -0.7999, -0.8405, -1.2275, -1.5443, -1.4625,
				]							)
				# fmt: on

				lowerCamelCase__								=		self._load_datasamples(1							)
				lowerCamelCase__								=		self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()							)
				lowerCamelCase__								=		feature_extractor(__lowerCAmelCase       ,  return_tensors='''pt'''							).input_features
				self.assertEquals(input_features.shape       ,  (1, 5_8_4, 2_4)							)
				self.assertTrue(np.allclose(input_features[0, 0, :3_0]       ,  __lowerCAmelCase       ,  atol=1E-4							)							)



