'''simple docstring'''

import torch
from torch import nn





class 							lowercase						(						nn.Module ):


   def __init__(   self				:	List[Any]   ,		__lowerCAmelCase				:	str   ,		__lowerCAmelCase				:	Optional[int]   ,		__lowerCAmelCase				:	str   ,		__lowerCAmelCase				:	int   ,		__lowerCAmelCase				:	Tuple=1   ,		__lowerCAmelCase				:	Optional[Any]=False)      ->					Optional[int]:
         super().__init__()

         lowercase_     =      n_token
         lowercase_     =      d_embed
         lowercase_     =      d_proj

         lowercase_     =      cutoffs + [n_token]
         lowercase_     =      [0] + self.cutoffs
         lowercase_     =      div_val

         lowercase_     =      self.cutoffs[0]
         lowercase_     =      len(self.cutoffs) - 1
         lowercase_     =      self.shortlist_size + self.n_clusters

         if self.n_clusters > 0:
               lowercase_     =      nn.Parameter(torch.zeros(self.n_clusters   ,		self.d_embed))
               lowercase_     =      nn.Parameter(torch.zeros(self.n_clusters))

         lowercase_     =      nn.ModuleList()
         lowercase_     =      nn.ParameterList()

         if div_val == 1:
               for i in range(len(self.cutoffs)):
                     if d_proj != d_embed:
                           self.out_projs.append(nn.Parameter(torch.FloatTensor(__lowerCAmelCase   ,		__lowerCAmelCase)))
                     else:
                           self.out_projs.append(__lowerCAmelCase)

               self.out_layers.append(nn.Linear(__lowerCAmelCase   ,		__lowerCAmelCase))
         else:
               for i in range(len(self.cutoffs)):
                     lowercase_ ,							lowercase_     =      self.cutoff_ends[i], self.cutoff_ends[i + 1]
                     lowercase_     =      d_embed // (div_val**i)

                     self.out_projs.append(nn.Parameter(torch.FloatTensor(__lowerCAmelCase   ,		__lowerCAmelCase)))

                     self.out_layers.append(nn.Linear(__lowerCAmelCase   ,		r_idx - l_idx))

         lowercase_     =      keep_order


   def __UpperCAmelCase       (   self				:	Tuple   ,		__lowerCAmelCase				:	Any   ,		__lowerCAmelCase				:	Optional[int]   ,		__lowerCAmelCase				:	Any   ,		__lowerCAmelCase				:	Optional[Any])      ->					str:
         if proj is None:
               lowercase_     =      nn.functional.linear(__lowerCAmelCase   ,		__lowerCAmelCase   ,		bias=__lowerCAmelCase)
         else:
               # if CUDA_MAJOR <= 9 and CUDA_MINOR <= 1:
               lowercase_     =      nn.functional.linear(__lowerCAmelCase   ,		proj.t().contiguous())
               lowercase_     =      nn.functional.linear(__lowerCAmelCase   ,		__lowerCAmelCase   ,		bias=__lowerCAmelCase)
               # else:
               #     logit = torch.einsum('bd,de,ev->bv', (hidden, proj, weight.t()))
               #     if bias is not None:
               #         logit = logit + bias

         return logit


   def __UpperCAmelCase       (   self				:	List[str]   ,		__lowerCAmelCase				:	List[Any]   ,		__lowerCAmelCase				:	List[Any]=None   ,		__lowerCAmelCase				:	Dict=False)      ->					str:

         if labels is not None:
               # Shift so that tokens < n predict n
               lowercase_     =      hidden[..., :-1, :].contiguous()
               lowercase_     =      labels[..., 1:].contiguous()
               lowercase_     =      hidden.view(-1   ,		hidden.size(-1))
               lowercase_     =      labels.view(-1)
               if hidden.size(0) != labels.size(0):
                     raise RuntimeError("Input and labels should have the same size in the batch dimension.")
         else:
               lowercase_     =      hidden.view(-1   ,		hidden.size(-1))

         if self.n_clusters == 0:
               lowercase_     =      self._compute_logit(__lowerCAmelCase   ,		self.out_layers[0].weight   ,		self.out_layers[0].bias   ,		self.out_projs[0])
               if labels is not None:
                     lowercase_     =      labels != -100
                     lowercase_     =      torch.zeros_like(__lowerCAmelCase   ,		dtype=hidden.dtype   ,		device=hidden.device)
                     lowercase_     =      (
                         -nn.functional.log_softmax(__lowerCAmelCase   ,		dim=-1)[mask].gather(1   ,		labels[mask].unsqueeze(1)).squeeze(1)
                     )
               else:
                     lowercase_     =      nn.functional.log_softmax(__lowerCAmelCase   ,		dim=-1)
         else:
               # construct weights and biases
               lowercase_ ,							lowercase_     =      [], []
               for i in range(len(self.cutoffs)):
                     if self.div_val == 1:
                           lowercase_ ,							lowercase_     =      self.cutoff_ends[i], self.cutoff_ends[i + 1]
                           lowercase_     =      self.out_layers[0].weight[l_idx:r_idx]
                           lowercase_     =      self.out_layers[0].bias[l_idx:r_idx]
                     else:
                           lowercase_     =      self.out_layers[i].weight
                           lowercase_     =      self.out_layers[i].bias

                     if i == 0:
                           lowercase_     =      torch.cat([weight_i, self.cluster_weight]   ,		dim=0)
                           lowercase_     =      torch.cat([bias_i, self.cluster_bias]   ,		dim=0)

                     weights.append(__lowerCAmelCase)
                     biases.append(__lowerCAmelCase)

               lowercase_ ,							lowercase_ ,							lowercase_     =      weights[0], biases[0], self.out_projs[0]

               lowercase_     =      self._compute_logit(__lowerCAmelCase   ,		__lowerCAmelCase   ,		__lowerCAmelCase   ,		__lowerCAmelCase)
               lowercase_     =      nn.functional.log_softmax(__lowerCAmelCase   ,		dim=1)

               if labels is None:
                     lowercase_     =      hidden.new_empty((head_logit.size(0), self.n_token))
               else:
                     lowercase_     =      torch.zeros_like(__lowerCAmelCase   ,		dtype=hidden.dtype   ,		device=hidden.device)

               lowercase_     =      0
               lowercase_     =      [0] + self.cutoffs
               for i in range(len(__lowerCAmelCase) - 1):
                     lowercase_ ,							lowercase_     =      cutoff_values[i], cutoff_values[i + 1]

                     if labels is not None:
                           lowercase_     =      (labels >= l_idx) & (labels < r_idx)
                           lowercase_     =      mask_i.nonzero().squeeze()

                           if indices_i.numel() == 0:
                                 continue

                           lowercase_     =      labels.index_select(0   ,		__lowerCAmelCase) - l_idx
                           lowercase_     =      head_logprob.index_select(0   ,		__lowerCAmelCase)
                           lowercase_     =      hidden.index_select(0   ,		__lowerCAmelCase)
                     else:
                           lowercase_     =      hidden

                     if i == 0:
                           if labels is not None:
                                 lowercase_     =      head_logprob_i.gather(1   ,		target_i[:, None]).squeeze(1)
                           else:
                                 lowercase_     =      head_logprob[:, : self.cutoffs[0]]
                     else:
                           lowercase_ ,							lowercase_ ,							lowercase_     =      weights[i], biases[i], self.out_projs[i]

                           lowercase_     =      self._compute_logit(__lowerCAmelCase   ,		__lowerCAmelCase   ,		__lowerCAmelCase   ,		__lowerCAmelCase)
                           lowercase_     =      nn.functional.log_softmax(__lowerCAmelCase   ,		dim=1)
                           lowercase_     =      self.cutoffs[0] + i - 1  # No probability for the head cluster
                           if labels is not None:
                                 lowercase_     =      head_logprob_i[:, cluster_prob_idx] + tail_logprob_i.gather(
                                     1   ,		target_i[:, None]).squeeze(1)
                           else:
                                 lowercase_     =      head_logprob[:, cluster_prob_idx, None] + tail_logprob_i
                                 lowercase_     =      logprob_i

                     if labels is not None:
                           if (hasattr(self   ,		"keep_order") and self.keep_order) or keep_order:
                                 out.index_copy_(0   ,		__lowerCAmelCase   ,		-logprob_i)
                           else:
                                 out[offset : offset + logprob_i.size(0)].copy_(-logprob_i)
                           offset += logprob_i.size(0)

         return out


   def __UpperCAmelCase       (   self				:	Optional[int]   ,		__lowerCAmelCase				:	Any)      ->					Tuple:
         if self.n_clusters == 0:
               lowercase_     =      self._compute_logit(__lowerCAmelCase   ,		self.out_layers[0].weight   ,		self.out_layers[0].bias   ,		self.out_projs[0])
               return nn.functional.log_softmax(__lowerCAmelCase   ,		dim=-1)
         else:
               # construct weights and biases
               lowercase_ ,							lowercase_     =      [], []
               for i in range(len(self.cutoffs)):
                     if self.div_val == 1:
                           lowercase_ ,							lowercase_     =      self.cutoff_ends[i], self.cutoff_ends[i + 1]
                           lowercase_     =      self.out_layers[0].weight[l_idx:r_idx]
                           lowercase_     =      self.out_layers[0].bias[l_idx:r_idx]
                     else:
                           lowercase_     =      self.out_layers[i].weight
                           lowercase_     =      self.out_layers[i].bias

                     if i == 0:
                           lowercase_     =      torch.cat([weight_i, self.cluster_weight]   ,		dim=0)
                           lowercase_     =      torch.cat([bias_i, self.cluster_bias]   ,		dim=0)

                     weights.append(__lowerCAmelCase)
                     biases.append(__lowerCAmelCase)

               lowercase_ ,							lowercase_ ,							lowercase_     =      weights[0], biases[0], self.out_projs[0]
               lowercase_     =      self._compute_logit(__lowerCAmelCase   ,		__lowerCAmelCase   ,		__lowerCAmelCase   ,		__lowerCAmelCase)

               lowercase_     =      hidden.new_empty((head_logit.size(0), self.n_token))
               lowercase_     =      nn.functional.log_softmax(__lowerCAmelCase   ,		dim=1)

               lowercase_     =      [0] + self.cutoffs
               for i in range(len(__lowerCAmelCase) - 1):
                     lowercase_ ,							lowercase_     =      cutoff_values[i], cutoff_values[i + 1]

                     if i == 0:
                           lowercase_     =      head_logprob[:, : self.cutoffs[0]]
                     else:
                           lowercase_ ,							lowercase_ ,							lowercase_     =      weights[i], biases[i], self.out_projs[i]

                           lowercase_     =      self._compute_logit(__lowerCAmelCase   ,		__lowerCAmelCase   ,		__lowerCAmelCase   ,		__lowerCAmelCase)
                           lowercase_     =      nn.functional.log_softmax(__lowerCAmelCase   ,		dim=1)

                           lowercase_     =      head_logprob[:, -i] + tail_logprob_i
                           lowercase_     =      logprob_i

               return out







'''simple docstring'''

def __a (	__lowerCamelCase			:						list[int] ,		__lowerCamelCase			:						int				)	->							bool:
      '''simple docstring'''


      lowercase_     =      len(__lowerCamelCase				)
      lowercase_     =      [[False] * (required_sum + 1) for _ in range(arr_len + 1				)]

      # for each arr value, a sum of zero(0) can be formed by not taking any element
      # hence True/1
      for i in range(arr_len + 1				):
            lowercase_     =      True

      # sum is not zero and set is empty then false
      for i in range(1 ,		required_sum + 1				):
            lowercase_     =      False

      for i in range(1 ,		arr_len + 1				):
            for j in range(1 ,		required_sum + 1				):
                  if arr[i - 1] > j:
                        lowercase_     =      subset[i - 1][j]
                  if arr[i - 1] <= j:
                        lowercase_     =      subset[i - 1][j] or subset[i - 1][j - arr[i - 1]]

      return subset[arr_len][required_sum]


if __name__ == "__main__":
       import doctest

       doctest.testmod()






